Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 2 [3] 4 5 ... 43

Author Topic: Anouncing The PathFinder Project  (Read 96304 times)

Dae

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #30 on: October 13, 2009, 04:35:57 pm »

Just adding my two cents, perhaps I'll have time for a few ideas later.

Here is some explanation about the pathfinding algorithm used in Baldur's Gate, amongst others.
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #31 on: October 13, 2009, 04:53:47 pm »

Thanks for the link Dae, I recommend everyone give it a thorough read.

Quote
It is not as important, however, if our computed path is sub-optimal (longer) than the current best-path method.

To a degree yes I agree that we do not necessarily have to have the optimal path, a path that's just slightly longer can be adequate.  The extra length of any path returned vs the length of the optimal path can be expressed as a percentage.  For example if the optimal path is 100 long and the found path is 106 units long that means 6% inefficiency.  We should at the very least measure this value and ideally be able to set the acceptable level of inefficiency and get a useful trade off as a result.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #32 on: October 13, 2009, 05:27:42 pm »

Heres another page from the same university as the above paper, lots of documentation and code for an A* implementation but I don't think it's the one in the above paper, rather its a generic A*.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

Symmetry

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #33 on: October 13, 2009, 05:32:42 pm »

As you say Impaler, I think the most obvious way to improve hierarchical A* is a better heuristic.

One thing that always annoys me in DF is the way rocks for making rock craft are taken from the nearest tile.  A better heuristic could help select rocks which are actually closer, reducing the need for lengthy paths.  The shorter the path the quicker to calculate after all.  I realise this is slightly outside the scope of the project.

The Node tree idea is interesting, but I feel it solves the easiest problem.  We can already find paths, and we can already sort-of find paths between nodes in a A* hierarchy without too much difficulty.  Improving the speed of this i good but improving the accuracy of the heuristic will give us more benefit.  The improvement we should concentrate on relates to how the nodes in the hierarchy are calculated.  At what point do we break a single node in two?  At what point do we coalesce? 

One huge advantage of using a node based hierarchy for DF is that we can split nodes around variable terrain features.  eg. Drawbridges.  But further it would be possible to split nodes at locked doors or at the water's edge.  Then we can treat different nodes as connected or not based on whether the path-finder in question can swim or can break down doors.

Also, and most usefully, it seems like we could split the nodes at points that help increase the accuracy of rough heuristic calculations.  If the distance between two nodes is say 10 units across another node, but the heuristic naively uses the size of that in between node and guesses at 100 units, when we finish finding the path and discover how large the error is we can split that node to improve the heuristic in future.

I'm a bit fuzzy about how you handle coalescing, and mainly quickly detecting a coalesce is desirable.  Also the exact way you'd split a node with more than a single tile border is fuzzy too.
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #34 on: October 13, 2009, 06:37:33 pm »

Quote
I'm a bit fuzzy about how you handle coalescing, and mainly quickly detecting a coalesce is desirable.  Also the exact way you'd split a node with more than a single tile border is fuzzy too.

That's cause I'm still fuzzy on it myself, as was hinted at earlier I see the rectangular areas as being the leaf nodes.  The splitting and merging of these nodes will be necessary as the map changes but exactly how it would be handled I'm not quite sure.  Their seems to be a method called "Framed Quadtree" that could be of use here.

As for the heuristic I was wondering if it would be possible to store a great deal of pre-computed heuristic data inside the nodes of the tree structure I'd been describing.  A really simple solution is to just store a value in each node that comes from estimating the travel time inside the node, for a leaf node this would be the 1/2 hypotenuse of the areas sides.  Larger nodes would just mash together the lower level heuristics and divide again.  In essence this would be a rough estimate of the distance across the node and once the common ancestor node (the lowest level node that contains both end points) is found returning its value would at least tell us if a proposed path is very long or very short.  That might be a bit better then using Manhattan as the heuristic. 

A more sophisticated heuristic would be to actually do a bit of A* pathing and store the results, say for each combination of Inter-2-Inter connections within a node (for example Node A connects to B, C and D so a test would be done for B<>C, C<>D, D<>B across the area of A and stored in A.  This would allow any proposed path to be estimated by summing up a large number of small legs and be much more accurate, though at the cost of more memory and cycles spent on updating each time the map changes.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #35 on: October 14, 2009, 02:35:50 am »

Hello. Just quickly chipping in my 2 bits' worth:

You were talking about the subdivision into space, mentioning convex regions and rectangles. I am using a third approach which I call "trivially connected zones". A TCZ is a region where a dorf can always reach any other tile in the TCZ by simply moving stupidly towards that tile - including "sliding around" obstacles in a least-resistance manner, like dumb homing enemies in Chip's Challenge or Nethack. Thus pathing costs within a TCZ are negligible, and TCZs can be potentially much larger than convex areas - a whole outdoor forest with sparse trees, for example, can be one TCZ, where it would be hundreds of rectangles or convex zones. Indoors, a large room with single-tile or two-tile workshop obstacles can likewise be a single TCZ.
Pathing is reduced to an A* search over the gateway tiles connecting TCZs. The paths are not optimal - in fact the theoretical inefficiency is up to 50% - but in practice the inefficiency should be much smaller. I've yet to do extensive statistical tests.

There's an algorithm for computing maximal TCZs from a seed tile. It's not precisely inexpensive, but it's local in nature and so won't be too expensive in upkeep.
Logged
Alpha version? More like elf aversion!

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #36 on: October 14, 2009, 02:39:21 am »

Also, though the hierarchical clearance algorithm linked earlier is interesting, I have a feeling that its practical utility is limited to "outdoor" environments, that is environments where obstacles are few and free space is the rule. I think it will not work so well underground - or at least, the selection of blocks must be made more clever. But I may be missing something in the description.
Logged
Alpha version? More like elf aversion!

DeathOfRats

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #37 on: October 14, 2009, 03:36:25 am »

My reason for mentioning convex zones was that, much like your TCZs, it's trivial to pathfind within it. Heck, even calculating path lengths from one point to another is trivial within a convex figure. I like the TCZ idea, though, since it does seem to solve a few of the problems with convex zones (I hadn't even considered trees, or columns within a room - oops?).

Mind linking us to the TCZ algorithm you mention?
Logged

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #38 on: October 14, 2009, 04:55:59 am »

Well, I'm not aware of anyone else having implemented it but that may not be because they haven't... I'm very bad at finding related works :)
As for my implementation, it is rather rough around the edges and I'm still working on it.
But basically, the idea is: Start with assuming all the world belongs to the TCZ. Move outwards from the seed tile, and whenever a tile conflicts (that is, it wouldn't be possible to silly-move from it toward some other tile in the TCZ), forbid either it or the other tile, depending on which is closest to the seed. Then backtrack to reprocess any neighbors of newly forbidden tiles.
Keep it up until the whole world has been processed.
That's the gist of it, though there are many obvious simplifications that can be made.
Logged
Alpha version? More like elf aversion!

DeathOfRats

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #39 on: October 14, 2009, 05:21:51 am »

Hmm, so basically it's a modified floodfill at first. But I've got a question: how far do you check for conflicts? Because if you have to check with every single tile in the TCZ, that's exponentially higher as the size of the TCZ goes up, which is pretty much unacceptable.

The check could be done locally (say, on a 10x10 tile grid, which would mean a limit on the exponentiality of the thing), but then I don't think it would be too difficult to find a situation in which the silly-move requirement was violated.

Or would it be better to just limit the size of a TCZ to something we can manage? Is there something I am misunderstanding?
Logged

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #40 on: October 14, 2009, 05:34:30 am »

Well, what you actually do is check each of the 8 (or so, depending on what silly-move strategy you use) sectors around the tile at a time, and forbid the entire sector wholesale if it comes to that; also, in each sector, you only need check those tiles that are closer to the seed than the current tile is. And that number grows sub-linearly with the size of the TCZ.
So it's not exponential - but even if it were, that wouldn't mean "unacceptable" right off - remember this is a one-time calculation, in principle, and its time complexity is much less important than the cost of pathing itself. Besides, the larger the TCZs, the fewer they are.

Anyway, you can bound the time taken by limiting the maximum size of the TCZ from the start, reducing the "whole world" to just a 30x30 grid or something like that. You wouldn't be able to cover the whole forest then, but hey.
Logged
Alpha version? More like elf aversion!

Alexhans

  • Bay Watcher
  • This is toodamn shortto write something meaningful
    • View Profile
    • Osteopatia y Neurotonia
Re: Anouncing The PathFinder Project
« Reply #41 on: October 14, 2009, 06:53:31 am »

How do you guys propose to deal with live terrain modifications?  If there weren't any you could just calculate the paths every few turns but as it is it seems like a permanent calculation... Is there any way to work around this?
Logged
“Eight years was awesome and I was famous and I was powerful" - George W. Bush.

DeathOfRats

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #42 on: October 14, 2009, 07:08:21 am »

That's part of the problem, and why I'd say it's important for whatever algorithm is chosen to have two characteristics: that segmentation works locally (i.e., I just mined a tile, I don't have to recalculate all the pathing for the whole damn world), and that different areas can be re-zoned (divided or merged). If those two criteria are met, it shouldn't be a problem to deal with terrain modifications.

Incidentally, that's part of my criticism to Sunken's TCZ (an idea which I otherwise like very much). I don't think you can realistically have TCZs (much) bigger than whatever size you're using for the local checking, since it makes it easier for the silly-move requirement to be violated (a little bigger might be possible, but I don't think you could, say, have a TCZ the size of a 2x2 z-level if you're doing 24x24 local checks, even if there is some overlap between the checks - overlapping would cost CPU time, but it would result in more robust segmentation, I'd expect).

Still, and like Sunken says, I don't see why we couldn't limit these TCZs to a size that's manageable locally (say, 12x12 or 24x24), and then use a hierarchical pathing algorithm like the one in the paper Dae linked us to (awesome paper, btw - I looked for a few others in the same vein in the IEEE paper database, and found a couple I want to read, but I didn't find any quite as impressive).
Logged

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #43 on: October 14, 2009, 08:33:19 am »

I don't quite understand what you mean by "local checks".

How you'd deal with changing terrain is more or less like this:
When a tile changes, find the TCZ(s) it contacts (use an efficient bounding-box algorithm for quick lookup).
Resume TCZ processing for all neighbors of the changed tile (and itself, if it was cleared) and process from there as before.
Finally, check tiles from which TCZs have withdrawn. If any remain uncovered by a zone, re-seed them until coverage is reestablished.

This will (unmodified) not reclaim space as aggressively as restarting the TCZ from scratch, but that may be just as well - maybe that tile will close up again anyway.
Logged
Alpha version? More like elf aversion!

Shades

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #44 on: October 14, 2009, 09:09:09 am »

That's part of the problem, and why I'd say it's important for whatever algorithm is chosen to have two characteristics: that segmentation works locally (i.e., I just mined a tile, I don't have to recalculate all the pathing for the whole damn world), and that different areas can be re-zoned (divided or merged). If those two criteria are met, it shouldn't be a problem to deal with terrain modifications

I think you'll be okay with convex zone / TCZ (the TCZ reads to me as basically how you use convex zones in most real life cases at any rate) under this regardless of size.

A new tile mined out is almost always adding to zone or creating a new zone, and building a construction (or growing a tree) is a simple check to see if it can be just ignored (ie not adjacent to another no-move square).

In the worst case, which will happen when players build walls for the most case, you can just recalcuate the TCZ and it's not a slow calculation as it's a single plane (I wouldn't recommend a TCZ that spans z-levels even though it's technically possible with ramps) and you can start from the point of dividing the zone into four with this new block as the corner (it should be trivial to decide which corner based on which adjacent sides it is blocked on)
Logged
Its like playing god with sentient legos. - They Got Leader
[Dwarf Fortress] plays like a dizzyingly complex hybrid of Dungeon Keeper and The Sims, if all your little people were manic-depressive alcoholics. - tv tropes
You don't use science to show that you're right, you use science to become right. - xkcd
Pages: 1 2 [3] 4 5 ... 43