Print

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

[blue sam3]

Could you not mark every junction (defined as an edge/corner of an open space with a path running off it or a joining of corridors) as a node, cache the distances between those nodes, then when pathfinding is called, simply pathfind from the dwarf to the nearest node, do the same from the job destination, then pathfind between the points (much quicker than actually doing the pathfinding due to the relative simplicity of the network) and return the path?

[thisisjimmy]

Mind you, the stepped-line algorithm is O(n), and A* is at best O(n) if we're explicitly moving on a non-obstructed path---decays toward O(n²) as the amount of deviation increases.  In addition, A* has the memory overhead of tracking where it needs to search (open set), where it has searched (closed set)---both of which a stepped-line algorithm lacks.

Specifically, routing around a tree will typically only add 2 nodes per tree to the open set when searching over the interesting set.  Both nodes are diagonal neighbors, so pathing between them is effectively a no-op.

Right, I meant that you could use A* if you choose to ignore larger clusters. If you're only ignoring single trees, don't use A*, because it's already trivial to go around the obstructions.  If you choose to ignore obstructions up to 3x3 tiles, A* might be handy.  You would only be using A* to path between interesting nodes. A* will be close to O(n) because there are no large obstacles between interesting nodes. Here's an example that shows how many tiles A* might search when routing around 3x3 obstacles:


In comparison to how many tiles A* searches when there are larger obstacles:


There's no question that stepped-line is faster than A*.  That's the trade-off of ignoring larger clusters. You get fewer interesting nodes, but pathing to an interesting node takes a bit longer.

[czolus]

Ran your two cases through, and had it spit out pretty pictures.
Legend:

• White: Passable tile.
• Black: Impassable tile.
• Dark Green: Start location.
• Light Green: End location.
• Blue: Path chosen.
• Yellow: Interesting node that is part of the path.
• Light Grey: Interesting node that is not part of the path, or being searched.
• Red: Interesting node in closed-set.
• Pink: Interesting node in open-set.

For kicks, here's what it spit out for A* over the same.  It appears I use a different h() for estimating distance than you did. (Both of the algorithms I ran use the same h())




Update: Didn't realize how little work my algorithm actually does til I had it print pictures including the open-/closed-sets.

[thisisjimmy]

The images really illustrate how much faster your method is! I'm surprised you're only seeing a 10x improvement on DF maps.

How do you find the initial set of interesting nodes that have line of sight to the start of the path? Do you use quadtrees?

Here's an example where I think it might be helpful to ignore small obstacles. I just drew this in paint. I didn't actually code your algorithm.

Spoiler (click to show/hide)

The red squares are the nodes that would be interesting if you ignore small obstacles. The cyan lines show how many interesting nodes might have line of sight to a tree if small obstacles generate interesting nodes. I only drew one cyan line to each tree for legibility.

[czolus]

If its not cached, I'm using a full iteration over the interesting node set to determine which interesting nodes I can reach from a given non-interesting node.  That's largely why I'm only getting a 10x speedup---figured that out around 2am.  Something to work on in the wee hours of the night.

I suppose its possible to eliminate interesting nodes for single impassable tiles altogether, without having to use A*:  If the stepped line algorithm detects an impassable step, check if that impassable location is a singleton (cache-able result), and if so, generate some arbitrary route-around.  Won't work as cleanly on non-singleton obstructions, but interesting point efficiency increases with obstruction edge-length.  Needs to know if the obstruction is a singleton in order to freely generate a route such that it doesn't have to perform searching for itself (which would negate much of the speedup).

More, I need to modify my pathing algorithm to properly generate stepped-lines in the 3D space.  Right now, I consider that a node may have up to 10 neighbors (NSWE, diagonal, up, down), which implies that all z-plane connections are interesting, and thus require A*.  Hilly regions become Hell(y).  Move to 26-neighbor and a 3D stepped-line, and blam, free ramp pathing w/o need to resort to as much A*.

Update: [strike]Quadtrees aren't looking promising.  They're very efficient about answering "does this line segment hit anything?" (O(log n), where n is the number of impassables), but no better than enumeration (actually, worse: i * O(log n) vs. i * O(v) where i is the number of interesting nodes, n is the number of impassables, and v is the average step-distance from our point to any interesting point.  Mind you, on a typical map n >> v.) at answering that question for n different objects.  Unless I'm missing something.[/strike] I'll make something work.

[thisisjimmy]

Right, I see the problem with quadtrees.  I hadn't really thought about it.

I can't think of any good solutions for that right now.  It may be possible to divide the map into regions that would let you prune interesting nodes quickly, but I don't know how to make that work.  You could also sacrifice finding optimal paths and only consider nearby interesting nodes (which can be done quickly with spacial partitioning). The idea here is that nodes that are very far away are the least likely to have line of sight.  It's not a great solution though because there are too many cases where it will find bad paths.

What about nodes on different z-levels? You could probably ignore a lot of those. No point in checking every node in every underground cavern when your dwarf is just walking around above ground.

[czolus]

Re-wrote all of my testing code from the ground up---original version was purposely brittle (quicker to write).  A more solid 10x speed improvement over A*.  Really both algorithms benefited, as the overall memory footprint is smaller, with fewer phantom objects.  Still no "free-pathing" around single impassables, but that will come.  And when it does, I can eliminate that many more interesting points.  I'll try to remember to package up my code & upload later for people to toy with.

Right, I see the problem with quadtrees.  I hadn't really thought about it.

Still, worth checking.

I can't think of any good solutions for that right now.  It may be possible to divide the map into regions that would let you prune interesting nodes quickly, but I don't know how to make that work.  You could also sacrifice finding optimal paths and only consider nearby interesting nodes (which can be done quickly with spacial partitioning). The idea here is that nodes that are very far away are the least likely to have line of sight.  It's not a great solution though because there are too many cases where it will find bad paths.

Dividing into regions is what I chose to go with.  Not very efficient time-wise, but only have to do it infrequently (or, in the case of my testing, once).  Highly parallelizable, thankfully, and can use the interesting node set as the seed points for growing the regions (which are just ordinary rectangles).  A node can belong to multiple rectangles, and if uses them to determine which interesting points it will pursue.  Oh, for flair, interesting points that border a rectangle (including diagonally) are considered part of that rectangle's interesting set---this helps prevent really, really weird paths in complicated maps where there may only be one interesting node per rectangle.

What about nodes on different z-levels? You could probably ignore a lot of those. No point in checking every node in every underground cavern when your dwarf is just walking around above ground.

Since I don't yet support diagonal pathing that spans z-levels, this is a trivial thing to factor out for.  The beauty, my code didn't have this in its first version... YEAHHHH.

[thisisjimmy]

Sounds like the algorithm is working out pretty well. You should go over a checklist of the various situations and corner cases you might need to handle.  Here's what I can think of at the moment:

• Does it support flying units? You'll probably need to look for interesting nodes on the walls and ceilings of caverns.
• Does it update efficiently when the environment is altered? Moving liquids can cause a lot of modifications, so updating has to be fast.
• Does it handle all possible terrain including mountains, cliffs, caves and any other configuration you can imagine?
• Dwarves slow down when they pass each other on the same tile.  Does your algorithm allow them to path around each other?
• Does it allow for different types of movement rules? For example, amphibious creatures can path through water and pets cannot path through certain doors.
• How does the worst case processing time compare to A*?
• How does the worst case memory usage compare to A*?
• Are the paths found always near optimal?

Seems like you have most of those questions handled.  I'm still hoping that you can get a bit more than a 10x speedup.  It seems like it should be possible, given how many nodes can be eliminated over A*.

[MrShovelFace]

just mod cats to have no legs then everyone's problems will be fixed 

[czolus]

Sounds like the algorithm is working out pretty well. You should go over a checklist of the various situations and corner cases you might need to handle.  Here's what I can think of at the moment:

• Does it support flying units? You'll probably need to look for interesting nodes on the walls and ceilings of caverns.

At present, no.  That will be resolved in the next stage, when I add support for diagonal vertical movement.  This will also ease support for hills (in effect, making them uninteresting).  Aquatic- and magma-pathers will be done after flying, as they'll be functionally identical, just using a different set of interesting points.

• Does it update efficiently when the environment is altered? Moving liquids can cause a lot of modifications, so updating has to be fast.

Based on Toady's posts, static water---lakes, rivers which flow without drainage except at edge-of-map---cause no particular constraints, as internally little if anything gets modified.  Last I checked, the only tiles which might be considered truly in flux are the ones at the drain end of a river, but they'll typically be static with respect to aquatic and ground passability.  However, bridges, floods and the like are strongly volatile, but I've not yet begun to incorporate mutation in the map.  I can already see a fairly clean way to handle volatile restrictions to movement---like doors---by dynamically toggling an interesting node's passability and/or interesting status without modifying routing tables.  Long-term mutations---digging, and the like---will warrant permanent routing table changes.

More to the point, calculating if an interesting node is a constant-time operation.  Calculating the region(s) if belongs to... that I have no idea how long it will take, as I'm currently not over-pleased with my current region system (its around O(n^3) slow, but for typically small n).  Calculating its neighbors is O(ri), where r is the average number of regions an interesting point belongs to, and i is the average number of interesting points in a region.

• Does it handle all possible terrain including mountains, cliffs, caves and any other configuration you can imagine?

So far, yes: Cliffs simply have a point where neighbor nodes stop, and there's thus no line-of-sight past that point.  Hilly/mountainous regions are handles at present, but are currently no more efficient than the current A* algorithm until I get diagonal vertical pathing implemented.

• Dwarves slow down when they pass each other on the same tile.  Does your algorithm allow them to path around each other?

Both possibilities are eligible---but that's more a concern for the local movement AI.  The global pathing AI would hand out the route (calculated in full when requested), the local one would be responsible for minor course corrections as its being executed---up to, and including, requesting a new path if the current one becomes invalid.

• Does it allow for different types of movement rules? For example, amphibious creatures can path through water and pets cannot path through certain doors.

The system will need to track 3-4 sets of interesting nodes:

• Ground-nodes.
• Aquatic nodes.
• Magma nodes.
• (Possibly) Arial nodes.  These may not be necessary, as a flier will use the ground nodes when on the ground, and will not need any nodes if its pathing to a z-level above terrain (natural or artificial).

Pets will require a somewhat special case, in that when generating a global path, door restrictions will need to be respected.  I recommend this be implemented as a completely separate pathing routine, because despite its similarity, you don't want a conditional nested so deeply in a fast-spinning loop (like A*) unless it really is required.

• How does the worst case processing time compare to A*?

Worst case occurs on a 3-tile path that does not have line-of-sight.  Run time is approx 2x, but the time-to-compute for both A* & mine are so small, its hard to get a good figure.

• How does the worst case memory usage compare to A*?

This I've not tested, yet.  Worst case for static allocation (needed at all times, and thus saved in the map itself) would be ~O(nm), where n is the number of interesting nodes, and m is the average number of interesting nodes connected to.  If you're caching paths between interesting nodes (which I advise), worst case for memory is nearer ~O(nmp), where n & m are as above, and p is the average # of nodes between n & m.

• Are the paths found always near optimal?

As optimal as A* with the same heuristic function.

Seems like you have most of those questions handled.  I'm still hoping that you can get a bit more than a 10x speedup.  It seems like it should be possible, given how many nodes can be eliminated over A*.

I traced most of this down to being a result of an inefficiency that I accidentally carried over from version 1 of my code, and realized while I was writing a response:
My algorithm first checks to see if the nodes share a line-of-sight.  Which currently, I do not have optimized to use the regions, so it currently takes O(p), where p is the number of nodes on the line-of-sight path from start to finish---whereas, I could instead check if the nodes belong to a common region, a small O(r), where r is the average number of regions a node belongs to,  usually < 3.  Win.

One open question I have, for Toady: what are the costs for cardinal (NESW), diagonal and vertical moves?

[Vattic]

Could your algorithm deal with multi-tile creatures such as wagons and siege engines?

[thisisjimmy]

To clarify about modifying the environment, I was thinking of a player using floodgates to flood and drain areas repeatedly. That's what could cause pathing changes.  I didn't mean rivers, which are always impassable. I just chose my words poorly.

Your solution for doors and bridges is elegant, but it would be hard to apply to areas that player drains or floods. You don't know if the player intends the flooding to be temporary or permanent. It's probably best to treat that situation like digging.

Could your algorithm deal with multi-tile creatures such as wagons and siege engines?

Multi-tile creatures could probably be handled with another set of interesting nodes.  You could generate those interesting nodes by "growing" all obstacles. In other words, all tiles that are next to a blocked node are considered blocked themselves.  This is assuming that multi-tile creatures are 3x3.

Worst-case memory usage:
It's possible for each interesting node to connect to most other interesting nodes.  This might happen in a forest, if you weren't going to ignore 1x1 obstacles.  It could still happen if you have a "forest" of 2x2 obstacles.  Luckily, this isn't likely.  In this scenario, O(nmp) becomes O(n²p).  The number of interesting nodes could be large in a worst case scenario.
However, A* has a pretty bad worse case memory usage. In the worst case, it has to search every reachable tile on the map.  Each one has to be stored in the closed set.  So I'd expect your algorithm to generally use less memory than A*.

Optimal path:
I think if you ignore single tiles when finding interesting nodes, and diagonal movement has a higher cost, you can end up with slightly sub-optimal paths. It shouldn't make much difference though.

The checklist looks pretty good, other than maybe fleshing out some details on how to modify the environment efficiently.

[blue sam3]

One open question I have, for Toady: what are the costs for cardinal (NESW), diagonal and vertical moves?

All are currently 1.

[czolus]

One open question I have, for Toady: what are the costs for cardinal (NESW), diagonal and vertical moves?

All are currently 1.

Good to know.  That can lead to some very interesting looking paths.

[EnigmaticHat]

One open question I have, for Toady: what are the costs for cardinal (NESW), diagonal and vertical moves?

All are currently 1.

Good to know.  That can lead to some very interesting looking paths.

I just did some quick arena tests where I put identical creatures in pairs that were set apart by straight/diagonal paths of identical length, and then one-stepped until they reached each other.  The ones on the straight paths always reached the each other before the ones on the diagonal paths.

So moving diagonally is definitely slower than moving along a straight line.