GoogleCodeExporter
commented
9 years ago Now working on path planning using A* search algorithm. It is essentially a BFS
(breadth first search) using a function of distance and some sort of other
heuristic measurement function. In this case, our distance is defined as the
distance between the current location and the target measured in delta-axis
summations and our heuristic function is left undefined as it is unimportant in
our case. Searching in the x-z plane is left as a regular value, while all
depth searching is
To clarify: if the source is at world position (-5, -5, -5) and our sink is at
(5, 5, 5), our "distance" is defined as the change in each axis; for x it is a
change in 11 units, y is 11, z is 11; in total it is 33 units for a dwarf to
travel. The reason why we do this is that a regular sqrt-distance function
might prematurely search into a depth area before searching other valid
locations. For example imagine a long hallway, with a staircase at the front
and a staircase at the back. The source is near the initial staircase, and the
sink is below the second staircase, but the staircases below aren't connected.
Without this heuristic the algo. will search deep into the first staircase
wasting a ton of time. If the sink is changed to be below the first staircase,
the dwarf knows not to search the rest of the hallway it has a low priority
compared to the near-by staircase.
Current solution ideas: create a hard-limit to the time given for searching, so
after a second or so it gives up and goes with the "best" position, but this is
dangerous as it could trap a dwarf in a location that constantly returns bad
computations in the end... other idea is to spawn threads so it has all the
time in the world, and A* will eventually give a solution, just might take
minutes and thus is a game breaker.
Another solution, but very different, would be to use D*: maintain a "hidden"
path-planning world per-dwarf and update the weights as the world is changed;
though this has a dramatic speedup, the memory usage is a killer...Original comment by nin...@gmail.com on 18 Nov 2011 at 7:13
Original issue reported on code.google.com by
nin...@gmail.comon 15 Nov 2011 at 9:01