Print

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

[Niseg]

I wrote a little maze navigation simulator in JavaScript (I really like's JS advantages )  in order to present a working demo for path finding optimizations. I got it to a level it's working "OK" and has some functional features. I'm still trying to add more features and organize it. It's generally a few pieces of code I slapped together and you may find it useful.

You can find the latest version here previous one was ~50:

this is on my wife's  payed site (reliable):
http://niseg.moshela.com/test_maze.html
I got the latest version here too(old free site I used):
http://niseg.50webs.com/test_maze.html
This one is back up and also  has older versions (test_maze1.html through test_maze37.html ):
http://niseg.0adz.com/test_maze.html

if you are adventurous you should try the 128X128 version the A* optimization made it run in acceptable time but it doesn't seem to work on my cellphone/android pda:
http://niseg.moshela.com/test_maze128.html

Demos:
- different heuristic different path -when using a* you'll notice that heuristic that overestimate the distance fail to find the shortest path. it also has a simple waypoint demo and 4~ room traversal path.
- big maze - A* likes getting lost here. You can  see how waypoint based path caching and room pathing is generally better and the smoothing algorithm also does a decent job here. You'll also notice the problem with waypoint based room and bad selection (working on it).




Current features:

UI(frontend)
- build a maze 32X32 by toggling points or lines if you click edges

-CSS support - I can added graphic an option to use Mayday's  tile-set  TXT by refresh button.

- brush selection using select box or buttons
- basic line/rectangle drawing  drawing.  violet start point default is filled rectangle can be toggled using buttons.
- drawing traffic input -toggle checkbox to see them.
Load/Save
- quick link generation with controllable length. Changed from v01 to v02 to B64 saves start,end and waypoints (max is 8 supports 15).
-quick link load is backward compatible (hex str,v01 and v02).
-quick link now has 2 more formats (well actually 3) v03 is a run-length encoded v02 maze data and v05 is a move to front encoded as 2,6 (3bit or 7bit) of the entire parameter. when a link is added it generates v02 and pick the shorter between v03 and v05
- forum output generation with controllable size - includes all the text in the table and paths
Pathfinding
- A* navigation with feedback on how many nodes were visited (shows complexity). I modified 46 dogs' implementation a tad lot.Farther optimized! The complexity of the original algorithm got aggressively reduced by using an O(1) lookup on closed and open queues (replace O(N) search) and all nodes are inserted in order to the open list (O(log N) insert, O(1) pop, O(1) search for minimum) . This made it run 1000 times faster on huge mazes.
 
- A* navigation with Traffic zones
- A* navigation on an edge map with correct selection and correct heuristics but it still looks at "center points"  that is not always center atm.
- A* in 2 room navigation - a node blocked if it's not in destination or source room (better than a range limit)
- modified heuristic currently defaults to sqrt(dx²+dy²),current options are (active button yellow): (dx²+dy²), sqrt(dx²+dy²),Manhattan , Max(dx,dy), Max(dx,dy) + Min(dx,dy)/4 , los penalty vector.
- feedback about path length ( I think I added this to both pathing algorithm)
-Waypoint navigation using a waypoint to waypoint full cache with feedback on number of nodes visited (path-finding,adding waypoint,updating cache). Full cache update will display it's size in steps (currently saved in "4 byte format" can be reduced to 4bit or less).
- waypoint navigation with path smoothing using vectors . I used info from this page. changed my line drawing to return a vector on action 0. Then I used the line drawer to draw lines and validated the return value. After debugging it works great and the complexity isn't  bad .
- path smoother chops off loops before starting (sort,find equal idx, first loop idx 0, last linear searched from end)
- waypoint-room path-finding (checkbox enabled to see "rooms") - this uses an idea I outlined in path finding thread it's like waypoint pathfinding but the cached paths are only from one room to its neighbor. The implementation is preliminary - need some more work. I got problem with "room" selection process (same as waypoint) which cause trouble with arbitrarily placed nodes(might use length limited A*). Current implementation selects rooms mathematically (e.g. x*number_rooms/width).

-room based navigation path currently working on some level it's called "advanced WP rooms". It uses path chaching but picks rooms by using bitmap
- "advanced rooms no cache" is a non path caching algorithm that looks are the first access point of to the destination room (saved in room) .The output shows the subpath using "O"  instead of a *.

Backend
- maze is an array of column format is [ y ][ x ] (a_star uses x,y maze so i swap the output values)
- all points are 2d arrays of format [x,y](converted from y<<16|x) - can be later changed to 3d format if needed
- file list :  test_maze.html , testmaze.js ,testmaze.css , a_star.js.


features I'm working on:

- room based navigation without using path caching but it uses saved access points to the next room . It uses A* to navigate between the access points which is low complexity.
-added BFSCollider function that outputs bellow the maze - it show "rooms" it finds and a clear button to remove it. It has a highlight button (debug feature) that let you kinda see how the the way the rooms are defined (yellow rectangle with cyan corners but the cyan corners can be overwriten)
-trying to figure how to shorten the qlink more so I can stick traffic zones in there.

future plans(somewhat prioritized) :
- improve refresh of drawing so it won't be so heavy.

- path validation and path replanning for waypoints along
- better  waypoint selection - current method uses heuristics which can fool the waypoint path-finder much like it fools A*
- improving path smoothing - currently trying to find ways to optimize path smoother and understand some mixed results.
- scrolling the maze - ui change to let users change mazes.
- fix waypoint removal bug.
- add other path finding algorithms like D* lite /LPA*

- forum input maze
- maze presistance "code" shortening
history:
 You should check  around page 12 of path finding thread in suggestion forum for more info about my plans and the little history of this little program.

I'm saving previous versions of my implementation by renaming them to test_maze#.html  . I now have 1 through 11 or 12 on my site if you want to see what i did in older versions.

I'll be happy to get any type feedback. I'll also be happy to get suggestions and feature requests especially on UI,input and output features. Any new ideas related to path finding should go in the path finding thread (we may want to start a wiki page to outline our progress) .

[Ethicalfive]

Hey! Just wanted to say, your doing some great work there Niseg! I'd like to see multiple paths and destinations to test out how well different path finders fair under load. How they react to changes etc.

Definately not an easy task your taking on, I certainly don't have the courage for it. Would be beautiful to see some opimisations that can help make the game more FPS friendly! Imagine having hundreds of dwarfs and herds of animals in a fort that wont become FPS-0!

[Dutchling]

Is this supposed to happen? (yellow is drawn by me)

Spoiler (click to show/hide)

[pugi]

From what i can see is that you are not using the A* algorithm (which is optimal, it always finds the shortest route), you a simple greedy algorithm that chooses the next node with the shortest distance to the target. The A* algorithm also adds the distance from the starting node (the distance traveled) to the cost of the next move.

[Aerval]

From what i can see is that you are not using the A* algorithm (which is optimal, it always finds the shortest route), you a simple greedy algorithm that chooses the next node with the shortest distance to the target. The A* algorithm also adds the distance from the starting node (the distance traveled) to the cost of the next move.

No, I've seen similar issues. May be the code is broken (I definitely press "Find Path A*)
Another problem I have seen might be that it sometimes doesn't go the linear way (and more zickzack)

Spoiler (click to show/hide)

This doesn't change the distance between two points but if my dwarfs go this way it would look odd.

I've one thing I don't understand in the path-finding discussion. Do you know for sure that Today uses an unfavorable algorithm? Just wonder about this point because I sometimes thougt that it could be not a problem of the algorithm but the game-engine.

By the way: Great project

[pugi]

Sorry if my last post was a bit unclear, i mean that the simulator is not using the A* search algorithm, when you click on it. I mean, paths like this can't even be explained with the zigzag distance = straight distance.

Spoiler (click to show/hide)

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.

[Niseg]

Edit: found the problem - the heuristic was messed-up. I changed it from a squared vector to Manhaten. You can change it now with simple buttons  (I'm a fan of the KISS method). Note that the results of what I posted below may have changed.

I changed a few things and made it a tad easier to change "paint modes".
The quicklink is now b64( I'm still spitting blood after debuging it).

I should have thought how to use the quicklink feature ,because it took me a while to redraw the maze(click on it to load it I used max link LOL).

I don't think there is something wrong with the code I got it from a blog you can look at the original here. I added a very minor change which counts the number of times the code  looks at a node.

I think the maze just is just a complex variation of a double comb maze (added start/dest save  yay )
it looks like this:

Spoiler (click to show/hide)

##############
#S+++++#D++++#
#+##########+#
#++++++#+#+#+#
#+######+#+#+#
#++++++#+#+#+#
#+######+#+#+#
#++++++#+#+#+#
#+######+#+#+#
#++++++#+#+#+#
#+######+#+#+#
#++++++++++++#
##############

This maze  will get you really close to worst case 74 node traversal (it's 75 when destination is blocked). It's design fools A* which assumes that the path exists in the node closest to the destination which fools it to go into all the dead end.

I think I might modify A* a tad and make a few variations of it including traffic zones. I think my first change would be to change heuristic and let you select it. The heuristic function is  now an dx²+dy² without the sqrt.

I can probably add more search algorithms. if I find some laying around. If you want to take a look at what waypoints can do to your test maze  check this link. You'll notice it's not the shortest path  but the waypoint  for that I need to add a path smoothing scheme.  Waypoint selection is also a problem much like a* being fooled by heuristic waypoint selection does to . Another thing you'll notice when you compare the "node visited " field. For waypoint navigation it's 15 and for A* it's 161.

btw has anyone tried this "maze" in  game  ?

[pugi]

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.


But the problem was indeed your heuristic. The function dx²+dy² always overestimates the distance to the destination, which is not allowed. It even says so in the comments. So sqrt(dx²+dy²) should also work and give the shortest way, also it should always try to move towards the destination diagonally and make zigzag-movement, but as both diagonal and straight movement have the same cost, it doesn't matter for the overall length of the path.
The Manhattan heuristic should also NOT work, because it also overestimates the cost, because it doesn't include diagonal movement, which would be two straight moves for Manhattan.
Another heuristic you could use would be min(dx, dy): because you can move diagonally with the same cost as straight movement, only the longest distance of x and y defines the overall distance.
The code for that would be

Code: [Select]

Math.min(Math.abs(current_node.x - destination.x), Math.abs(current_node.y - destination.y))

Edit:
I forgot to add this, i found a nice java applet for the comparison of different search algorithms. It is in German, but you should be able to use it without problems, i couldn't find any other with the amount of features it has. http://www.stefan-baur.de/cs.web.mashup.pathfinding.html
Sadly you can only draw obstacles with a 3x3 brush, but it doesn't really change anything. Something nice about it is that it also shows all the nodes visited and not just the final path.

[Quietust]

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;

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

[Aerval]

Isn't the A* Algorithm always optimal? When you look at this and compare vector and manhattan, there must be something wrong???

[pugi]

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

Yes, that wouldn't take that into account. But the simulation is already built in the way that a move to each of the 8 possible sides costs 1. And using the other formula wouldn't change anything, because floor(sqrt(2)) = 1.
If you want to take that into account you would have to increase the default movement cost to 100 or something, so a diagonal move has the cost 141.

Isn't the A* Algorithm always optimal? When you look at this and compare vector and manhattan, there must be something wrong???

Yes, the A* Algorithm is always optimal, i said so in the first reply. I don't know what heuristic is used when selecting "vector" and the heuristic "Manhattan" (normally defined as cost = dx + dy) would overestimate the remaining distance to the goal, which is not allowed in most if not all pathfinding algorithms. You can only use the Manhattan distance as a heuristic when the allowed moves are up/down/left/right.

[Niseg]

I hope you noticed I fixed the heuristic function (manhaten by default).  I tried to make  some silly heuristic but it  didn't work too well  .

I'm going to try to get a path smoother for waypoint cache I think I'll try something simple like of my path to waypoint is length l I'll try to find a path from step l/2 to step 3l/2 . I'll just use A* and see  how heavy it is. I can also try to check the vector first (greedy) to check if I can hit the target by going "straight" to it (I think I'll do it after the A* because A* is already coded).

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.

Isn't the A* Algorithm always optimal? When you look at this and compare vector and manhattan, there must be something wrong???

Well it's a matter of the guidance the heuristic gives. You'll notice that the vector heuristic ,sqrt(dx²+dy²), is not only computationally intensive to compute it also took 50% more node visits than Manhaten. 

Edit:
I forgot to add this, i found a nice java applet for the comparison of different search algorithms. It is in German, but you should be able to use it without problems, i couldn't find any other with the amount of features it has. http://www.stefan-baur.de/cs.web.mashup.pathfinding.html
Sadly you can only draw obstacles with a 3x3 brush, but it doesn't really change anything. Something nice about it is that it also shows all the nodes visited and not just the final path.

Really nice it Shows you how misguided those algorithms can be . The greedy one tend to hit any wall and go around it.

and about A* optimizations I can probably optimize it to run faster or better but it's not really my intention. JS is slow anyways and I'm not planning to reinvent A* just use it as a working algorithm.  I might try to get more search algorithms in like D* etc but i want to finish my waypoint scheme . It would be another way to improve game performance much like traffic but it would take a lot less work for the user than traffic designation.

[pugi]

Sigh... i tried to make it clear to you, Niseg:
You can not use the Manhattan distance heuristic when you can move diagonally!

A heuristic calculates the approximate distance from the current point to the destination. You can not chose a heuristic, that overestimates the remaining distance; that means the result of the heuristic has to be less or equal to the real number of remaining steps. If you choose a heuristic that overestimates the cost, you can't be sure if you get an optimal solution / the shortest path.
For the Manhattan heuristic the distance for a diagonal move is 2: 1 to the side and 1 up/down, while the distance for a horizontal/vertical move is 1. It doesn't know that you can also move diagonally. So if the destination would be 10 tiles south-west of the start, the heuristic would calculate the cost 20 (10 steps south, 10 steps west), while the real distance would be 10 (10 steps south-west).

I can show you an example where you can see the problem:
http://niseg.0adz.com/test_maze.html?maze=v02AUAUAQETEwAAAAAAAAAAAAAAAAAAAAAAAAP_wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Here the Manhattan distance chooses to go diagonally towards the wall, then straight east to the end and then straight south to the destination. The heuristic doesn't know, that it can also move diagonally so it chooses the shortest way for only vertical/horizontal movement.
When you choose the vector heuristic, it correctly calculates the shortest path, by moving diagonally and left of the wall.

And i know that the sqrt(dx² + dy²) is harder to calculate, just use the other heuristic i recommended: max(dx, dy)

[Niseg]

You can use whatever you want but you'll probably get less than optimal results.

As you requested I added "max(abs(dx),abs(dy))" heuristic and made it more clear what the others are . I'm now also highlighting which one is being used. I also added some line drawing of walls and floors.

Anyways I got a good way to approximate square roots but it relies on a log2 which some processors can do (PowerPC has cntlz = count leading zeros) . A sqrt(dx^2+dy^2) is computationally intensive. I did this in an asm project we had to figure out an approximation of  sqrt(x) to get us line number of an integer triangle. I know that a number is a sum of a*2^i so i found the left most one and shifted the number right by half of it +1 (to be on the safe side) and started iterating from there - I beat the teacher's program  in terms of speed .

Max isn't a bad deal except when you dx and dy get close to eachother you underestimate by upto 40%. How about max(dx,dy)+min(dx,dy)/4. That one is pretty fast and it's not off by much.

when you are playing with my program you should keep note of the number of visits and compare it to path length (just added a print for that when visited nodes are updated).

[pugi]

Nice improvements you made there
I also noticed that the max(dx,dy) heuristic tries to get dx=dy... I had not thought about that, it looks a bit weird. But then i noticed that in some cases the max heuristic didn't get the optimal path, the vector path was one step shorter. That should not happen, as the heuristic never overestimates the cost and then i found the mistake.
The A* search algorithm you based your program on has a mistake in it: when you expand a node and find a neighbor that is already open list, it just skips that node. The algorithm forgets to check if the new path to the node is shorter than the one already on the open list. I guess that this was made to keep the open list small, as that doesn't happen very often, but it could lead to not being able to find the optimal path.
You can see an example of that happening in this maze.
The sqrt heuristic checks the left side of the wall first, as the neighbors there have a lower vector distance to the destination, while the max heuristic checks the right side of the wall first to try to keep dx = dy. After a few more expansions the max heuristic should also notice that going on the left side of the wall is shorter, but apparently the node below the small wall was first expanded from the node on the right, so the shorter path didn't get updated.

And trying to find an effective heuristic may be a bit complicated, i know