Print

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

[GeorgiaPeanuts]

I was reading the pathfinding is A* every tick of a dwarf moving must evaluate 26 positions.

A way to optimize the pathfinding is to precalculate long-distance paths, and as the map is modified by the player to update these paths. So instead if for instance there a long hallway and the dorf is at one end and the room he wants to get to is at the other end and off to the side. He would instead build a a path using the long-range pathfinding grid, so his whole travels through the hallway would just be moving towards the current end node of the path. The savings are that any path is a known passable area of traversal. So the dorf is not doing any pathfinding calculations as he passes through the hallway.

When he reaches the end of the hall. If there is another node in his path he will move towards that. The paths need not even be straight as it can be evaluated what tiles are contained by a direct line to line segment from two nodes. Each node would only generate paths to nodes within a certain distance horizontally and only a tile above and below vertically. So when you modify the map the generation of the nodegraph updating would be confined to a limited area.

The bulk of the nodegraph would be precalculated when you start a new embark using nodes at some corners and with some uniform spacing for open ground.

The final part is that the A* is still used once you are in the local region of where you intended to go. So if you reached the closest node in the nodegraph to the workshop you wanted it would then use the A* again to pathfind from the node to the workshop.

[NW_Kohaku]

We have had quite a few lengthy discussions of pathfinding and the flaws of A* in the past, to the point where most people are basically tired of rehashing the same thing. 

You would be better served looking over some of these threads, especially the bulk/latter half of this one:
http://www.bay12forums.com/smf/index.php?topic=76278.msg1932980#msg1932980
(This one has multiple different arguments for and against different methods, including vector pathing and the like, and specifically has arguments about why you can't store long-range pathing the way that you are talking about so easily.)

On Jump Point Search:
http://www.bay12forums.com/smf/index.php?topic=92732.msg2596082#msg2596082

And just a plain search page on pathfinding in general:
http://www.bay12forums.com/smf/index.php?action=search2;params=eJwtzDEOgCAMheG7uDg7eB4CbRUMAimoMenhLYbtf9_wLN42AaHMssgkjnutWtXnx0A-S6RGap0udxA0k1N8h2RuBgPrQqowRBdTpP-4E1kGr1hs81tIGNL-Afp_L1g.

[Niseg]

A way to optimize the pathfinding is to precalculate long-distance paths, and as the map is modified by the player to update these paths.........

Like NW_Kohaku we grinned this topic already. I made a demo of what you are describing . Check the my pathfinding simulator thread(in my signature) . I admit I need to write a clearer manual  and beautify the UI(slapped it together). I didn't touch this project for a year~.

You can check this link and toggle on draw rooms checkbox and then the refresh button(they are at the bottom of the buttons on the left).It will show you my implementation of what you are describing.

The stuff you are talking about is called "waypoint rooms" in my simulator. you can also use user placed waypoints and they have a list of path to all other waypoints. My algorithm for those is S->wp1->wp2->D. You can also use a waypoint room or a non caching room pathfinding( you can see the room structure below the maze). My simulator doesn't have an update scheme yet so after changing the maze click recreate WP rooms and path cache update.

Path caching is decent and it's fast but the no path penalty is the same as A*.A room navigation method does take some memory but it gives much better results than A* because it avoids dead ends.

[Kogut]

I was reading the pathfinding is A* every[citation needed] tick of a dwarf moving must evaluate 26[citation needed] positions.

[Niseg]

I was reading the pathfinding is A* every[citation needed] tick of a dwarf moving must evaluate 26[citation needed] positions.

I think that 26 came from path  step direction options and when he said tick he meant step. I also found that statement unusual.

If you can fly in DF and you are up in the air you got 9 path options above you,8 options at your level and 9 options bellow you. Because the complexity is approximately K^n or 26^n in that case A* can be extremely complicated.

BTW I saw your simulator. Does it use A* or JPS. Looking at that thread I might be able to push that JPS algorithm into my simulator. I still think a divide and conquer method with a dynamic update scheme can be optimal. I might go ahead and finish my implementation and then maybe add a 3rd dimension. 

[Kogut]

Because the complexity is approximately K^n or 26^n in that case A* can be extremely complicated

No, no, no. A* is NOT checking every possibility. And it is NOT executed for every unit, on every steep.

[thisisjimmy]

Sounds a lot like this: http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

I think it's been suggested before.

[NW_Kohaku]

Sounds a lot like this: http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

I think it's been suggested before.

HPA* was discussed thoroughly back in this thread.  This link is probably better at describing the topic, as well.

[Niseg]

Because the complexity is approximately K^n or 26^n in that case A* can be extremely complicated

No, no, no. A* is NOT checking every possibility. And it is NOT executed for every unit, on every steep.

On a grid the big O is like (k/2)^n but it doesn't check each step it just adds more nodes to its list until it finds the target. It always check the closest nodes first . maybe my implementation is less than optimal but on the map I posted above it checks almost 79% of the nodes( I guess it's an extreme case). My room algorithm ( I guess it's similar to HPA) looks at 21~% . When doing room base path caching it goes down to under 3% (most of what it does is copy cached paths).

What kills A* is when there is no path to the target and that's when simple path caching won't help but a room system can. (rooms = less nodes = shorter worst case).

[thisisjimmy]

On a grid the big O is like (k/2)^n but it doesn't check each step it just adds more nodes to its list until it finds the target.

How did you manage to implement pathfinding that takes exponential time, O((k/2)^n)?  What is n?  The path length?  The number of nodes expanded?  If the latter, you probably meant 26*n, which is simply O(n). 

What kills A* is when there is no path to the target and that's when simple path caching won't help but a room system can. (rooms = less nodes = shorter worst case).

DF handles this case by preprocessing the map and marking unconnected areas.  So it doesn't have to run pathfinding when there's no path to the target.

[kaenneth]

I've been working off and on on a dynamic 'room' allocation system, where a 'room' is a blob of adjacent open tiles.

The particular goal I'm working on is guaranteeing a stable state in a single update when a map changes; such as a door being locked/unlocked; while balancing blob side and solidity.

An example set of rules is a blob should have no more than 25 tiles, if it has more it gets split in half along it shortest dimension; that is, a 3X10 blob will get cut into two 3x5's; a blob should have no fewer than 10 tiles, if it does, it merges with the smallest neighboring blob.

My current goal is to ensure a merge doesn't trigger a split, which triggers a merge, which triggers a split... cascading through the whole map.

I'm also trying to refine the maximim size rule to be 'there must not be a path longer than x through a blob' so you can say that a path through 10 blobs will take no more than 100 steps for example; as well as maintaining a mapping of blob ajacancys for quickly determining if a path exists at all.

[NW_Kohaku]

How did you manage to implement pathfinding that takes exponential time, O((k/2)^n)?  What is n?  The path length?  The number of nodes expanded?  If the latter, you probably meant 26*n, which is simply O(n). 

n is path length.  And no, it really is exponential - if you look at graphs showing what tiles are actually searched during an A* search, a trip more than halfway around the fortress, especially if it is on different floors, or there is a trip that requires going down then back up or the like, will basically search nearly the entire fort on the way to trying to find the path to the target. 

That is to say, a trip of a hundred tiles might take testing ten thousand tiles for paths.

Most of these will be checking adjacent tiles to the paths that already exist for optimal path weights (1 weight instead of 2), checking into every single individual dead-end room in a residential sector, and nearly flood-filling the paths.

DF handles this case by preprocessing the map and marking unconnected areas.  So it doesn't have to run pathfinding when there's no path to the target.

Unfortunately, not really true - this is why resealing the HFS results in tremendous FPS lag, as the clowns will continuously try to path into the fortress they cannot reach.  Likewise, locking all the doors to keep diplomats out results in constant FPS drain as the diplomat keeps trying to path into your fortress, although since this is only one character, it's less notable. 

Again, all of this was handled quite in depth in previous threads espeically this one, and you would be better off reading and reviving that thread than continuing this one.

[thisisjimmy]

How did you manage to implement pathfinding that takes exponential time, O((k/2)^n)?  What is n?  The path length?  The number of nodes expanded?  If the latter, you probably meant 26*n, which is simply O(n). 

n is path length.  And no, it really is exponential - if you look at graphs showing what tiles are actually searched during an A* search, a trip more than halfway around the fortress, especially if it is on different floors, or there is a trip that requires going down then back up or the like, will basically search nearly the entire fort on the way to trying to find the path to the target. 

That is to say, a trip of a hundred tiles might take testing ten thousand tiles for paths.

Most of these will be checking adjacent tiles to the paths that already exist for optimal path weights (1 weight instead of 2), checking into every single individual dead-end room in a residential sector, and nearly flood-filling the paths.

That's polynomial, not exponential.  It should be roughly O(n^2) for a 2D grid, and O(n^3) for a 3D grid.  If it were truly O((26/2)^n), then finding a path that's only 7 tiles long would, at worst, have to search over 60 million tiles.  This is more tiles than there are in a standard 4x4 embark.

A path of length 100 might take testing 10,000 tiles, even if it only has to test on one z-level, because 100^2 is 10,000.

DF handles this case by preprocessing the map and marking unconnected areas.  So it doesn't have to run pathfinding when there's no path to the target.

Unfortunately, not really true - this is why resealing the HFS results in tremendous FPS lag, as the clowns will continuously try to path into the fortress they cannot reach.  Likewise, locking all the doors to keep diplomats out results in constant FPS drain as the diplomat keeps trying to path into your fortress, although since this is only one character, it's less notable. 

Again, all of this was handled quite in depth in previous threads espeically this one, and you would be better off reading and reviving that thread than continuing this one.

That's most likely because it marks unconnected areas for non-flying creatures.  Flying creatures ignore that information.  See this: http://www.gamasutra.com/view/feature/131954/interview_the_making_of_dwarf_.php?page=8