Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[LoSboccacc]

http://niseg.0adz.com/test_maze.html?maze=v02AgAgAQEQEEGQcJFQIIAxwAAAAAAMAAAAAwAAAPrmAQAAHAAAAAMAADAAwAAPAAAAAOAAgAACAQBBDAIAQDAEACDACAAhABAAIAAgABAAQAAQAIAAEAEAAAgCAAAIBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA


path with waypoint on this map also find a suboptimal solution.

[devek]

I know you guys would like to simulate the game but This isn't really the intent. I think a simple A* is fine because traffic zone only act as a guide. My main goal is to lower complexity enough by defining somekind system which can then be implemented in DF .I can change it to do traffic zone if you want - it can help you test stuff I think Toady does it with 2 bits(4 value) that are in a table. You can also download  the page and hit  it with your own axe  (it's messy) . I'm working on this page on and off and if you can help implement new features you are welcome to it.

DF's system works in 3d space. It can handle fliers, swimmers, monsters that can handle magma, and monsters that can break down doors and such. Traffic zones are not bits but weights that can be defined in d_init.txt

And as far as i know, DF uses the A* algorithm or some variant of it for pathfinding, it just doesn't check for obstructions when calculating the distance for job items like choosing a stone for a construct rock throne task. It would for example choose the rock in the z-level directly below the center of the workshop (distance 1), even when the dwarf would have to travel 20 tiles to the side to even get to the stairs.

Good thing too. If you have 2000 stones, its trivial to find a close one but not so trivial to check all 2000 for the shortest path. We talked about cool ways to address this a year ago or so in a different thread but a discussion of graphs is a little off topic in a thread about pathfinding. I'll just let you guys have fun and not troll this too much hehe.

[pugi]

Good thing too. If you have 2000 stones, its trivial to find a close one but not so trivial to check all 2000 for the shortest path. We talked about cool ways to address this a year ago or so in a different thread but a discussion of graphs is a little off topic in a thread about pathfinding. I'll just let you guys have fun and not troll this too much hehe.

I know why DF just checks the distance and not calculates the actual path and I've read that thread around the time when it was posted
I just want to help Niseg to get his simulator working nicely.

[Niseg]

Yesterday I started experimenting with path smoothing it's not that good using A* especially as I made the distance longer.  If subpath length is n and cached_path length is m I'm looking from subpath[m/2] to cached_path[m] or cached_path[n-m] . You can check my old waypoint example . You can probably  "kill it" if you want  with a setup that looks like this S+++ww+++D. You won't really kill it it would complained about undefined. I need to think about something better like post path generation scanning .

DF's system works in 3d space. It can handle fliers, swimmers, monsters that can handle magma, and monsters that can break down doors and such. Traffic zones are not bits but weights that can be defined in d_init.txt

I can convert the simulator to 3d but it's not worth my time . My simulator just look at passable/impassable nodes so it's a general case. Let me remind you I'm not trying to simulate df just make a pathfinding demo with similar algorithms that can be easily added into DF.

I'm sorry about being unclear about traffic designation. I meant the storage of those values in each node is probably  done using 2 bits (saves memory ) then the table of values looks like this:

Code: [Select]

int trafic[4]={1,2,10,25};


[rampaging-poet]

I added two waypoints to the map you just linked to, and the smoothed path by waypoints became much worse.  It's still not as bad as the unsmoothed path without those waypoints, but the path wandered down before heading back up when it could have gone in a straight line.

Maze is here

While your waypoint search checks less nodes, it can give some pretty weird results sometimes.

[Niseg]

  doh post got deleted....

I added two waypoints to the map you just linked to, and the smoothed path by waypoints became much worse.  It's still not as bad as the unsmoothed path without those waypoints, but the path wandered down before heading back up when it could have gone in a straight line.

Maze is here

I hope you didn't mind the fact I was updating it while you played with it. the Path smoothing is much better and works great . You can smooth the path again  using "walker smooth"( it's not A* need to fix text)  it to get a smoother path something you can see  in LoSboccacc's maze. you can also smooth the result of A* as needed.

Anyways about waypoint selection the current scheme isn't great I think I might use a specialized heuristic for like shoot a line from a waypoint to the start point and if it hits the wall penalize it's score. my sugestions is that This waypoint system is added to df to help player deal with extremely long paths.  I know a few clowns that would be happy to get some better guidance.  Waypoint placement is important because it's fooled by the heuristic function just like A* . This is something humans can do pretty well ( we can see the maze the computer doesn't).

While your waypoint search checks less nodes, it can give some pretty weird results sometimes.

There is a bug on removal I didn't fix yet so you should update path cache when changing it. I'll fix it later (I'd rather rush toward a better app ) . You should also update the path cache once changing the maze. I'm not doing auto validation of paths so if you put a wall in the center of the path it won't know about it....

[rampaging-poet]

Alright, that path caching bug would probably explain the mysterious teleporting dwarf.

By the looks of things, smoothed waypoint paths are generally pretty good, although it does depend on waypoint placement a bit.  They definitely visit less nodes than A* even when the path is suboptimal, and it will only pull farther ahead on a larger map.  What's the efficiency of the smoothing algorithm?

[Niseg]

Alright, that path caching bug would probably explain the mysterious teleporting dwarf.

If you look at future plans it's not as high a priority because I prefer to add new features than fixed bugs. It's still a very important part of the system because it has to support this kind of update  for it to work continuously.

By the looks of things, smoothed waypoint paths are generally pretty good, although it does depend on waypoint placement a bit.  They definitely visit less nodes than A* even when the path is suboptimal, and it will only pull farther ahead on a larger map. 

Yeah it's generally very good though I need to improve checking ends of lines . Yesterday I made it try one more node  when path is blocked    but I didn't update the website (changed line 1816 ). it made it take care of "teeth" better. 

What's the efficiency of the smoothing algorithm?

Line drawing is O(n) with fast ops (no mult,div,mod,sqrt) while the walker is also O(n) so it is at most O(n²)  but i think it's closer to a O(n²/2) because I couldn't find a worst case for  O(n²).  It keeps shooting lines from size 2 to n until it's blocked or blocked twice then it will advance forward to the node at the end of that line and try again. so It's about the sum of counting numbers which converge to n(n+1)/2 .

I also tested the runtime using chrome.
my reference click is toggle node which does a complex "redraw".
I used this maze :

               t    dt
toggle         32   0
a*             271  239
smooth         40   8
wp search      38   6
wp smooth      138  106

 
As you see it's generally not too bad. Javascript is still pretty bad for profiling stuff because it's slow. it has to interpet or runtime compile stuff and some complex operations like sqrt, multiply and divide take a lot less than their overhead while in reality . You'll still see that A* is a monster compared to path smoothing and wp search. The wp smooth seems a little excessive I do double smoothing (might not be necessary when I update code) when wp search is  done. When I try that step by step ,wp search,smooth1 , smooth2, I get dt of 13+12+22 = 47ms respectively .

As I said the results are not great because it's a scripting language ... Yesterday I successfully killed my  DF's FPS in a simple experiment by putting a few clowns in a very large cage .I approximate the complexity was 20*O( min(k^n,100000) ) I manged  to get the game to 50fps at the very beginning.

This example can show how  waypoint based path caching  can lower complexity . While the stored path is not optimal the smoothing algorithm fixes the path to be optimal.  A* visits 472 nodes while waypoint path visits 30 that's a factor of 15.7~.  A* has to do complicated stuff on each visit so reducing it's complexity would have great yield on FPS.

The main fix I think that would help DF is controlling worst case( no path to target)  and even a waypoint  can inform the pathfinder there is no path to any other waypoint which is enough for it to give up before killing your CPU in a node explosion search to nowhere.

[tps12]

Wouldn't that fail to take into account that diagonals cost sqrt(2) instead of 1 (which is definitely true in Dwarf Fortress)?

Source? I had also been under this impression, but someone challenged me on it and subsequent testing (running around in arena mode with a stopwatch) convinced me that diagonal moves cost the same as straight ones.

[Niseg]

The A* code looked fine, but i found something you can change:

Code: [Select]

new_node.g = current_node.g + Math.floor(Math.sqrt(Math.pow(new_node.x-current_node.x, 2)+Math.pow(new_node.y-current_node.y, 2)));Because you always only take one step in any direction and the cost for each step is currently always 1 you should change it to:

Code: [Select]

new_node.g = current_node.g + 1;And when you include traffic zones you can just change it to current_node.g + new_node.traffic or whatever.
[/code]

Done and I also added a way to add future support for traffic zones.

I changed the original function quiet a bit :
- limited length a_star search
- support for node based search (node has edges rather than neighbors)  I still need to fix the heuristic .
- added a mode for traffic zones (not implemented yet).

The paths data of waypoint nodes can be discarded to save room and then the problem would be reduced to from k^(x*w) to x*k^w. The current complexity is much lower more like 2*k^w + another k^w for the overhead map (it's 4X4 so it's much less than the subpath which is about 8X8 room).

The waypoint-room based path finding is my first step toward an automatic optimization of A*  it works quiet well but I didn't finish it. I predict problems if you block off the destination because the code doesn't check that yet...

[finka]

Here's an example where the current room algorithm apparently fails to find any path at all, in case that's helpful.

[kaenneth]

One thought on the floor(sqrt(x^2,y^2)), have you considered a lookup table? for the small area you have, and that it's all integer input and result, 1kb (32x32xa byte) of memory might (might, needs testing) be faster than those operations.

[Niseg]

Here's an example where the current room algorithm apparently fails to find any path at all, in case that's helpful.

here is a fixed link to that maze . I can't seem to access my old site(I should get a domain name...) and I'm not sure it's updated .

I agree that the room based algorithm needs work. The advanced version is off by a mile.I think i know why that happens - the heuristic for room base search is on the room map which means it doesn't evaluate the distance correctly.

EDIT: I figured it out it's because of the use of path caching from the center of rooms .  I'll add a search that doesn't use path caching . I might ad an access point parameter to the edges array and go for those. I'm also considering moving the central points or splitting very large rooms




I  also  another problem with  A* case for rooms  in this maze it doesn't find a path  to the destination because it only look in the "board" while the edges between rooms are not related to their location on the "board".

I'll fix both problems by tommorow. Thanx for the feedback! 

One thought on the floor(sqrt(x^2,y^2)), have you considered a lookup table? for the small area you have, and that it's all integer input and result, 1kb (32x32xa byte) of memory might (might, needs testing) be faster than those operations.

Heuristic performance is not a critical part of this simulation due to the fact JS is inherently slow . It might help if I run performance test by telling it to find path x times for example.  What i try to optimize are the node visits which is affected by the distance to the destination and the complexity of the maze(how well it fools A*).

The idea with overlaying room is to reduce both the distances and the edges. It also make a complex maze fairly trivial as you can see on the bottom.

[Grax]

[Niseg]

Thanx! That explains a few things.   I found the problem debugging a partial reconstruction of your maze- my insert - in order doesn't work    . The insert in order somehow corrupt the whole queue I'll probably remove/fix  it  today and upload my "redraw" optimization which would make drawing the maze and traffic zones a lot less computationally intensive (helps a lot with 128X128) .

The "insert in order" was my later optimization . I reduced the complexity from 198~  million iterations to about 1 million with my first optimization (on a big 128X128 maze). The insert in order only reduced it to 100000 so it's not as critical for performance. I just didn't want it to run for 13 seconds

EDIT : problem fixed. I disabled insert in order and then fixed it