| --- Log opened Mon Apr 15 00:00:39 2013 |
| 00:11 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Connection closed] |
| 00:15 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 00:15 | | mode/#code [+o himi] by ChanServ |
| 00:36 | | * iospace eyes McMartin's link |
| 00:44 | <~Vornicus> | tldr: "shit fuck" |
| 00:44 | <@[R]> | Was less amusing than I hoped |
| 00:44 | <&McMartin> | Also, South asian developers named "Danshit" |
| 00:45 | <&McMartin> | Which is kind of unfortunate |
| 00:45 | <@Azash> | I can imagine their job adverts |
| 00:45 | <@Azash> | "Now hiring junior PR managers: Do you appreciate a challenge?" |
| 00:52 | | Thalass|KSP is now known as Thalass |
| 01:20 | < RichyB> | Heh. Upside of allowing arbitrary Unicode in identifiers and having dependent typing: https://twitter.com/copumpkin/status/323581571632345088 |
| 01:31 | | VirusJTG_ [VirusJTG@Nightstar-09c31e7a.sta.comporium.net] has joined #code |
| 01:31 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 01:33 | | VirusJTG [VirusJTG@Nightstar-09c31e7a.sta.comporium.net] has quit [Ping timeout: 121 seconds] |
| 01:45 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 01:45 | | mode/#code [+o himi] by ChanServ |
| 02:03 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 02:17 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 02:18 | | mode/#code [+o himi] by ChanServ |
| 02:18 | | RichyB [richardb@Nightstar-86656b6c.cable.virginmedia.com] has quit [Ping timeout: 121 seconds] |
| 03:01 | | gnolam_ [lenin@Nightstar-b2aa51c5.cust.bredbandsbolaget.se] has joined #code |
| 03:01 | | gnolam is now known as NSGuest63130 |
| 03:01 | | gnolam_ is now known as gnolam |
| 03:01 | | NSGuest63130 [lenin@Nightstar-b2aa51c5.cust.bredbandsbolaget.se] has quit [Ping timeout: 121 seconds] |
| 03:01 | | mode/#code [+o gnolam] by ChanServ |
| 03:26 | | VirusJTG_ [VirusJTG@Nightstar-09c31e7a.sta.comporium.net] has quit [[NS] Quit: night] |
| 03:42 | | gnolam_ [lenin@Nightstar-b2aa51c5.cust.bredbandsbolaget.se] has joined #code |
| 03:42 | | gnolam is now known as NSGuest15688 |
| 03:42 | | gnolam_ is now known as gnolam |
| 03:42 | | mode/#code [+o gnolam] by ChanServ |
| 03:45 | | NSGuest15688 [lenin@Nightstar-b2aa51c5.cust.bredbandsbolaget.se] has quit [Ping timeout: 121 seconds] |
| 03:48 | | mac [mac@Nightstar-fe8a1f12.il.comcast.net] has joined #code |
| 04:00 | | Kindamoody[zZz] is now known as Kindamoody |
| 04:02 | | Thalass is now known as thalass|afk |
| 04:45 | | thalass|afk is now known as Thalass |
| 04:47 | | Thalass is now known as Thalass|KSP |
| 05:00 | | syksleep is now known as Syk |
| 05:32 | | Turaiel[Offline] is now known as Turaiel |
| 05:45 | | Thalass|KSP is now known as Thalaway |
| 05:55 | | ErikMesoy|sleep is now known as ErikMesoy |
| 06:02 | | Kindamoody is now known as Kindamoody|out |
| 06:18 | | mac [mac@Nightstar-fe8a1f12.il.comcast.net] has left #code ["Leaving"] |
| 06:30 | | Derakon is now known as Derakon[AFK] |
| 07:07 | | Thalaway is now known as Thalass |
| 07:43 | | Turaiel is now known as Turaiel[Offline] |
| 09:00 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 09:11 | | RichyB [richardb@Nightstar-86656b6c.cable.virginmedia.com] has joined #code |
| 09:13 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 09:13 | | mode/#code [+o himi] by ChanServ |
| 09:25 | | RichyB [richardb@Nightstar-86656b6c.cable.virginmedia.com] has quit [Ping timeout: 121 seconds] |
| 09:39 | | Kindamoody|out [Kindamoody@Nightstar-e9aa495d.tbcn.telia.com] has quit [Ping timeout: 121 seconds] |
| 10:01 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: Leaving] |
| 10:06 | | Thalass [thalass@Nightstar-f97b970e.bigpond.net.au] has quit [Ping timeout: 121 seconds] |
| 10:29 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 10:31 | | RichyB [richardb@Nightstar-228a334c.plus.com] has joined #code |
| 10:40 | | Thalass [thalass@Nightstar-f97b970e.bigpond.net.au] has joined #code |
| 10:42 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 10:42 | | mode/#code [+o himi] by ChanServ |
| 11:05 | | Thalass [thalass@Nightstar-f97b970e.bigpond.net.au] has quit [Ping timeout: 121 seconds] |
| 11:29 | | Thalass [thalass@Nightstar-f97b970e.bigpond.net.au] has joined #code |
| 11:45 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 11:58 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 11:58 | | mode/#code [+o himi] by ChanServ |
| 13:16 | | RichyB [richardb@Nightstar-228a334c.plus.com] has quit [Ping timeout: 121 seconds] |
| 13:17 | | RichyB [richardb@Nightstar-228a334c.plus.com] has joined #code |
| 13:38 | | RichyB [richardb@Nightstar-228a334c.plus.com] has quit [Ping timeout: 121 seconds] |
| 14:06 | | celticminstrel [celticminst@Nightstar-e83b3651.cable.rogers.com] has quit [[NS] Quit: KABOOM! It seems that I have exploded. Please wait while I reinstall the universe.] |
| 14:06 | | celticminstrel [celticminst@Nightstar-e83b3651.cable.rogers.com] has joined #code |
| 14:07 | | mode/#code [+o celticminstrel] by ChanServ |
| 14:37 | | RichyB [richardb@Nightstar-228a334c.plus.com] has joined #code |
| 15:02 | | ToxicFrog is now known as ToxicFrog|W`rkn |
| 15:06 | | EvilDarkLord [jjlehto3@Nightstar-a5db08cc.org.aalto.fi] has quit [Ping timeout: 121 seconds] |
| 15:14 | | EvilDarkLord [jjlehto3@Nightstar-a5db08cc.org.aalto.fi] has joined #code |
| 16:43 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 16:43 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 16:57 | | Thalass [thalass@Nightstar-f97b970e.bigpond.net.au] has quit [Ping timeout: 121 seconds] |
| 17:53 | | Derakon[AFK] [Derakon@Nightstar-a3b183ae.ca.comcast.net] has quit [Ping timeout: 121 seconds] |
| 17:55 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has joined #code |
| 17:55 | | mode/#code [+ao Derakon Derakon] by ChanServ |
| 18:13 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has quit [Ping timeout: 121 seconds] |
| 18:14 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has joined #code |
| 18:14 | | mode/#code [+ao Derakon Derakon] by ChanServ |
| 18:25 | | Syk is now known as syksleep |
| 18:38 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has quit [Ping timeout: 121 seconds] |
| 18:38 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has joined #code |
| 18:38 | | mode/#code [+ao Derakon Derakon] by ChanServ |
| 18:51 | | Turaiel[Offline] is now known as Turaiel |
| 19:24 | | RichyB [richardb@Nightstar-228a334c.plus.com] has quit [Ping timeout: 121 seconds] |
| 19:30 | | joshie [Jdale8@3CBAD0.289929.BC62B2.FEB1A6] has joined #code |
| 19:33 | | joshie [Jdale8@3CBAD0.289929.BC62B2.FEB1A6] has quit [[NS] Quit: ] |
| 19:35 | | RichyB [richardb@Nightstar-228a334c.plus.com] has joined #code |
| 19:54 | | Kindamoody|autojoin [Kindamoody@Nightstar-e9aa495d.tbcn.telia.com] has joined #code |
| 19:54 | | mode/#code [+o Kindamoody|autojoin] by ChanServ |
| 19:55 | | Kindamoody|autojoin is now known as Kindamoody |
| 20:02 | | Turaiel is now known as Turaiel[Offline] |
| 20:08 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has quit [Ping timeout: 121 seconds] |
| 20:08 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has joined #code |
| 20:08 | | mode/#code [+ao Derakon Derakon] by ChanServ |
| 20:24 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: Leaving] |
| 20:48 | | Kindamoody is now known as Kindamoody[zZz] |
| 20:54 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has quit [Ping timeout: 121 seconds] |
| 20:54 | | Derakon [Derakon@Nightstar-a3b183ae.ca.comcast.net] has joined #code |
| 20:54 | | mode/#code [+ao Derakon Derakon] by ChanServ |
| 21:22 | | * iospace glares at PXE |
| 21:22 | <@iospace> | why you no work! |
| 21:25 | | Derakon__ [chriswei@Nightstar-a3b183ae.ca.comcast.net] has joined #code |
| 21:25 | | * Derakon__ ponders a problem for Pyrel, the roguelike game he's been working on. |
| 21:26 | < Derakon__> | The problem is monster pathfinding, and more specifically how to do it efficiently even in extreme cases. |
| 21:27 | < Derakon__> | The current system generates a "heat map" that shows, for each cell, how far it is away from a goal cell (i.e. the player's position). |
| 21:27 | < Derakon__> | This is a simple breadth-first search across the map. |
| 21:27 | < Derakon__> | But for a 360x120 map that is mostly open space, it takes .15s to calculate, and it has to be recalculated on every turn. |
| 21:27 | <@jeroud> | iospace: Did you sprinkle enough pixie dust? |
| 21:28 | < Derakon__> | The problem is exacerbated by it being an open region -- it'd be faster if the map is mostly enclosed, but I want to be able to handle both efficiently. |
| 21:28 | <@iospace> | jeroud: you're hilarious |
| 21:29 | < Derakon__> | Of course, within an open region, the shortest path for a given cell is simply min(cost of getting to any exit to the region + cost of that exit to the goal). |
| 21:29 | <@iospace> | -_- |
| 21:29 | < Derakon__> | Figuring out how to work that into the overall algorithm is difficult, though, since it requires recognizing which cells are exits in the middle of doing the overall processing. |
| 21:30 | <@jeroud> | Derakon__: Cache the previous paths, check that all of them are still clear and then start searching back from the new target until you reach the old path? |
| 21:31 | < ErikMesoy> | Hmm. My first thought to split the map into quadrants of (moved away from), (moved towards) and (moved parallell to). The former doesn't need to be updated yet, because the shortest path is still to old location + continue from there. |
| 21:31 | < Derakon__> | Keep in mind that this solution has to work efficiently for many-to-one pathfinding. |
| 21:31 | < Derakon__> | I implemented A* originally, and it worked fine for 1v1 situations and similar, but becomes grossly inefficient as the number of monsters goes up. |
| 21:32 | < Derakon__> | The heat map has the big advantage of being calculate-once, use-many; each monster just examines its neighboring tiles and moves to the one with the lowest cost. |
| 21:33 | < Derakon__> | Getting clever about cached paths is one option but introduces a lot of complexity since you have to be very careful about when to invalidate the cache. |
| 21:33 | <@jeroud> | Derakon__: How does that handle bottlenecks? |
| 21:33 | < Derakon__> | Generally, by clustering around the bottleneck. |
| 21:33 | <@jeroud> | Cool. |
| 21:34 | < Derakon__> | But if you can make heatmap generation fast enough, then you can do things like maintaining multiple heatmaps so that e.g. orcs will all cluster around but a different monster type will try to path around. |
| 21:34 | < Derakon__> | (Or having 10 orcs cluster and the rest path around to pincer the player, etc.) |
| 21:34 | < ErikMesoy> | So you want to get clever about algorithm rather than caching? |
| 21:34 | < Derakon__> | Ideally. |
| 21:34 | < Derakon__> | Algorithms tend to be more generalizable than caching, for one. |
| 21:35 | < Derakon__> | I'd rather not introduce caches until things are much more set in stone. |
| 21:35 | < ErikMesoy> | Divide the game map into chunks, monsters in the same chunk as the player head for the player, monsters in another chunk head for the appropriate chunk edge/corner? |
| 21:36 | < Derakon__> | That's basically a node-based pathfinding system, and it could potentially help, yes. |
| 21:36 | < Derakon__> | You'd only generate the heatmap for the player's local area (a radius around the player), and use the nodes to navigate outside of that region. |
| 21:36 | < Derakon__> | You still need to recognize when the map has changed to introduce new shorter routes (e.g. due to tunnelling). |
| 21:37 | < ErikMesoy> | Updating on tunnelling seems more tolerable than updating on every move, at least |
| 21:37 | < Derakon__> | Yeah, it's a rarer event. |
| 21:38 | < Derakon__> | What I'd really like is some way to handle large open regions efficiently in the current algorithm, assuming there is such a way. |
| 21:38 | < Derakon__> | Since I think speed would be mostly acceptable otherwise. |
| 21:38 | < ErikMesoy> | Declare an open section to be a chunk that never needs updating because you cannot tunnel in it? |
| 21:38 | < Derakon__> | No, I mean in the current heatmap generation. |
| 21:39 | < Derakon__> | Which is a very simple breadth-first search. |
| 21:39 | < Derakon__> | Here: http://pastebin.com/tmR9UpdS |
| 21:40 | <&ToxicFrog|W`rkn> | It doesn't seem like it should take 150 whole milliseconds to scan ~43k cells. |
| 21:40 | < Derakon__> | Unfortunately my profiler doesn't do a good job of telling me where my time is going, either. |
| 21:43 | < ErikMesoy> | Check which quadrant the monster/tile is relative to the player, then check from pos-1 to pos+1 (instead of y+2) or pos to pos+2 as appropriate? That should roughly halve the number of tiles being searched |
| 21:43 | <@jeroud> | Derakon__: The big loop over all the cells, obviously.~ |
| 21:43 | < Derakon__> | Jer: well, yes. |
| 21:43 | < Derakon__> | Erik: breaks down in the event of multiple goal cells. |
| 21:44 | < Derakon__> | We may want the monster to path to e.g. nearest exit away from the player (if frightened), nearest ally (if allies asleep), etc... |
| 21:44 | <@jeroud> | Multiple goal cells means multiple heat maps, right? |
| 21:44 | < Derakon__> | No, it means multiple cells with a cost of 0 in the given heat map. |
| 21:45 | <@jeroud> | Ah. |
| 21:45 | < Derakon__> | All are assumed to be equally-valid destinations. |
| 21:48 | <@jeroud> | What about updating the heat map instead of regenerating it? |
| 21:48 | < Derakon__> | Every time the player moves, every cell would need to be updated. |
| 21:49 | < Derakon__> | And subtle movements can result in significantly different paths (when there's two valid paths of slightly differing cost). |
| 21:50 | <@jeroud> | Only until you reach a border with an area whose cost is determined by a different goal. |
| 21:50 | <&ToxicFrog|W`rkn> | Could python be generating some inefficient structures underneath you? What's the observed time complexity? |
| 21:51 | <@jeroud> | That's only a win in some cases, though. |
| 21:51 | < Derakon__> | TF: my test was done with 10x 360x120 maps that are completely open; that's 1.439s total (~.14s per map). |
| 21:52 | < Derakon__> | If I double it to 360x240 then the runtime is 2.986s. |
| 21:52 | <&ToxicFrog|W`rkn> | Derakon__: right; what I mean is, if you halve the number of cells, what does the performance do? |
| 21:52 | < Derakon__> | So basically, linear with map size. |
| 21:52 | <&ToxicFrog|W`rkn> | Aah. |
| 21:52 | < Derakon__> | Sorry, I had to rerun the tests. |
| 21:52 | < Derakon__> | (Well, linear with number of cells, to be clear) |
| 21:53 | <&ToxicFrog|W`rkn> | So it sounds less like something is bumping you up a complexity class and more that it's just slow. :/ |
| 21:53 | < Derakon__> | This is with running in Cython, note. |
| 21:53 | < Derakon__> | Previously it was about 3x worse. |
| 21:53 | <&ToxicFrog|W`rkn> | Pypy? numpy? |
| 21:53 | < Derakon__> | Already using numpy. |
| 21:54 | < Derakon__> | Unfamiliar with Pypy. |
| 21:54 | <&ToxicFrog|W`rkn> | Python JIT, IIRC |
| 21:55 | <@jeroud> | pypy is a high performance JITed Python VM. |
| 21:56 | <@jeroud> | It doesn't run numpy (too much C), but it ships with an implementation of quite a lot of the numpy core. |
| 21:56 | < Derakon__> | Numpy is mostly being used here to make interacting with ND arrays of numbers not painful. |
| 21:56 | < RichyB> | Derakon: what happens to the runtime if you replace cellQueue = [] with "import collections; cellQueue = deque()"? |
| 21:56 | < Derakon__> | But that said, I would really like to stick with the standard Python if possible. |
| 21:57 | < RichyB> | er, collections.deque() even |
| 21:57 | < RichyB> | ? |
| 21:57 | < Derakon__> | Since that's what all other third-party libraries are built against. |
| 21:57 | < RichyB> | (collections is in the standard python library) |
| 21:57 | < RichyB> | (numpy is very not, because it depends on all kinds of things like LAPACK) |
| 21:57 | < Derakon__> | RichyB: well, first my unit tests fail... |
| 21:58 | < RichyB> | It occurs to me that cellQueue might end up being fairly long, and you're using it as a queue. I think that .pop(0) copies the entire list one element down? |
| 21:58 | < RichyB> | oh, it's called .popleft() on deque |
| 21:59 | < RichyB> | deque(['a','b','c']).popleft() ~= (['a','b','c'].pop(0) |
| 21:59 | < Derakon__> | Go from 2.98s to 3.75s. |
| 21:59 | < Derakon__> | So in other words, performance is worse. |
| 22:00 | < RichyB> | Bummer. |
| 22:00 | < Derakon__> | I think the Python list type is seriously optimized to handle a ton of common use cases, and may in fact automatically detect this use case. |
| 22:02 | < RichyB> | I get about the same timing - 200ms - for this on a 320x120 grid. |
| 22:05 | < RichyB> | wtf |
| 22:05 | | * RichyB kicks cProfile |
| 22:05 | < Derakon__> | It doesn't tell you much. |
| 22:05 | < RichyB> | Idiot thing attributes 200ms to the getHeatMap() call - gee wiz that's useful - but only ~100ms to anything more detailed. |
| 22:06 | < Derakon__> | I'm impressed you got that much out of it. |
| 22:08 | < Derakon__> | I mean, it's telling me that I'm spending about 1.5s out of 8.5s calling either max() or min(), but everything else is pretty much zeros. |
| 22:09 | < ErikMesoy> | Is it practical to improve that by declaring an inaccessible space outside the map? |
| 22:09 | < Derakon__> | Yeah, that should be doable. |
| 22:15 | <@jeroud> | Derakon__: What if you track locations of enemies and stop building the heat map when it covers all those locations? |
| 22:17 | < Derakon__> | Mm, that would be an improvement, yes, but probably not much of one in most cases. |
| 22:17 | < Derakon__> | Especially since the monster spawner tries to put monsters far away from the player so the player doesn't notice their arrival. |
| 22:17 | < RichyB> | heh |
| 22:17 | < RichyB> | https://tech.dropbox.com/2012/07/plop-low-overhead-profiling-for-python/ sounds pretty interesting, right? |
| 22:18 | <@jeroud> | Also, maybe a sorted queue instead of an unsorted one? |
| 22:18 | < RichyB> | Actually, it's just the same information as cProfile only it only distorts your profile by about 0.1% rather than by 25-50% (unlike cProfile). |
| 22:18 | < RichyB> | Only reports which functions you're in, never what line you're on. |
| 22:19 | < Derakon__> | Hmph, adding the border makes it worse again. WTF. |
| 22:19 | < RichyB> | Probably still very useful for annoying frameworky programs. |
| 22:19 | < Derakon__> | (That is, adding a border of walls, and then removing the calls to min/max) |
| 22:19 | < Derakon__> | 3.016s -> 3.713s. |
| 22:20 | < Derakon__> | I guess the calls to max are overall cheaper than considering all those inaccessible border tiles? *shrug* |
| 22:20 | < Derakon__> | Or maybe making the padded array is killing me. |
| 22:20 | <@jeroud> | O(log(n)) rather than O(1) to insert new things into the queue, but it gives you better partial maps if you stop when you cover all the bad guys. |
| 22:21 | < Derakon__> | ...nahh, numpy.ones() is taking negligible time. |
| 22:21 | < Derakon__> | Jer: what does a sorted queue do for me? I'm doing a breadth-first search, so it's already sorted. |
| 22:23 | <@jeroud> | Whoops, I was thinking something silly. You're right. |
| 22:23 | <@jeroud> | For some reason I was imagining a variable cost. |
| 22:26 | | ErikMesoy is now known as ErikMesoy|sleep |
| 22:26 | < Derakon__> | Hm, on reflection, the approach I wanted to try (i.e. making the algorithm smarter about open areas) wouldn't solve the general problem anyway. |
| 22:26 | < Derakon__> | I mean, the algorithm's unacceptably slow in dungeons, which are like 98% closed space. |
| 22:27 | <@jeroud> | Stopping when all the enemies are covered gives you a variable win for a fairly small constant cost. |
| 22:28 | <@jeroud> | The win gets bigger over time as the enemies get closer. |
| 22:29 | <@jeroud> | Hrm. What if you built a dual map. |
| 22:30 | <@jeroud> | Start one map from goals and another from enemies, stop when they intersect. |
| 22:31 | < RichyB> | It'll be easier to implement A*. |
| 22:31 | < Derakon__> | That would give you a path for the closest enemy to any goal. |
| 22:31 | < Derakon__> | I've implemented A*; it's one-to-one and thus doesn't scale. |
| 22:31 | < RichyB> | How many goals do you have? |
| 22:31 | < Derakon__> | Depends on use case, but even with 1, having a dozen monsters each doing their own A* would be slower than doing 1 heat map. |
| 22:31 | < Derakon__> | And the game will have a lot more than a dozen active monsters. |
| 22:37 | <@jeroud> | Derakon__: You can cache previous maps and reuse them if the goals end up in the same places, I suppose. Invalidate the cache if the geography changes. |
| 22:37 | < Derakon__> | I suspect I'll have to switch to some kind of node-based approach, where the map is divided into regions and within a region you just use shortest-linear-distance. |
| 22:37 | < Derakon__> | Then use standard Dijkstra on the nodes, since the cost from one node to the next can be precalculated. |
| 22:38 | < Derakon__> | Bleh. Way more complicated. |
| 22:39 | <&ToxicFrog|W`rkn> | Hmm. I wonder how e.g. Nethack handles this. |
| 22:39 | <@jeroud> | Is there some feature of the geography you can use? |
| 22:39 | <&ToxicFrog|W`rkn> | ...possibly it just doesn't, since even bighroom levels are pretty small. |
| 22:39 | < Derakon__> | TF: probably by limiting its play region to under 80x24. |
| 22:40 | <@jeroud> | Rooms-and-corridors or something? |
| 22:40 | < Derakon__> | Angband similarly has a max map depth of 256, per one of the devs. |
| 22:40 | < Derakon__> | Jer: right, that's what the node map would be based on. |
| 22:40 | <@jeroud> | Ah. |
| 22:41 | <&ToxicFrog|W`rkn> | Derakon__: that doesn't really help for bigrooms, though, does it? |
| 22:41 | <@jeroud> | Doesn't seem prohibitively complex. |
| 22:41 | < Derakon__> | So the program gets handed a map of 0s and 1s (representing accessible/inaccessible), it examines the map to construct nodes (broadly, alternating between regions that have no walls and ones that do), runs Dijkstra on that. |
| 22:41 | <&ToxicFrog|W`rkn> | And from what you've said the non-bigroom case already has acceptible performance. |
| 22:41 | < Derakon__> | The non-bigroom case isn't acceptable IMO. |
| 22:41 | < Derakon__> | .07s/update for a dungeon level. |
| 22:42 | < Derakon__> | I mean, it's faster than the big room. |
| 22:42 | < Derakon__> | But roguelikes should not have lag. |
| 22:42 | < Derakon__> | This isn't the 1990s any more. |
| 22:42 | <@jeroud> | Rooms are nodes, corridors are costs and linear-distance all the things. |
| 22:43 | < RichyB> | Derakon: yer thing runs about 30% faster under pypy. :) |
| 22:43 | < Derakon__> | This runs into trouble for concave nodes. |
| 22:43 | < Derakon__> | Richy: good to know, thanks. |
| 22:43 | < Derakon__> | But I don't think I can reasonably switch interpreters away from the standard. |
| 22:43 | < Derakon__> | Also I get a 3x improvement by using Cython. |
| 22:44 | < Derakon__> | (Which is incorporated into all the numbers I've posted so far) |
| 22:44 | <@jeroud> | Derakon__: No, but it can make testing faster.~ |
| 22:45 | < Derakon__> | ...run a heat map for the node the player is in? |
| 22:45 | <&ToxicFrog|W`rkn> | 150ms/action doesn't really strike me as "lag"; a typical player probably won't want to go about 5aps or the like anyways |
| 22:45 | < Derakon__> | That would deal with convex nodes. |
| 22:45 | < Derakon__> | TF: running down corridors or other "autoexplore" mechanics. |
| 22:45 | < RichyB> | Derakon: why's cellToCost a dict instead of another ndarray? |
| 22:46 | < Derakon__> | Richy: had it as an array before, but earlier optimizing determined that dict lookup was faster, oddly enough. |
| 22:46 | < Derakon__> | Possibly because I was doing the lookup as cellToCost[coords], i.e. passing a tuple in. |
| 22:46 | < Derakon__> | I didn't test unpacking the tuple manually, I admit. |
| 22:59 | < RichyB> | Did you do anything to speed this up with Cython? |
| 22:59 | < Derakon__> | Nope, just use the Cython compiler at program start. |
| 22:59 | < RichyB> | At program start? |
| 23:00 | < RichyB> | Reason I'm asking is that I only see a ~30% improvement from throwing Cython at this with a 1024x1024 grid. |
| 23:01 | < RichyB> | Oh, I get a 100% speedup from Cython on a 320x120 grid. |
| 23:02 | < Derakon__> | 1024x1024 you may be running into memory management issues. :) |
| 23:02 | < Derakon__> | That's 4MB of data at 4bytes/cell. |
| 23:03 | < RichyB> | I have 6MB of cache on this chip. |
| 23:20 | | Thalass [thalass@Nightstar-f97b970e.bigpond.net.au] has joined #code |
| 23:57 | | Derakon__ [chriswei@Nightstar-a3b183ae.ca.comcast.net] has quit [[NS] Quit: leaving] |
| 23:58 | | VirusJTG [VirusJTG@Nightstar-09c31e7a.sta.comporium.net] has joined #code |
| --- Log closed Tue Apr 16 00:00:53 2013 |