Re: distance approximation in 3D


"Ray Dillinger" <bear@xxxxxxxxx> schrieb im Newsbeitrag
news:484cbac5$0$17152$742ec2ed@xxxxxxxxxxxxxxxxx
copx wrote:

This is meant to be used as the heuristic of an A* pathfinder.This is
speed critical. On a big 3D map with many actors this function will be
called countless times.
Pathfinding is probably the single most CPU intense task of the entire
code base.

If it is, then I humbly suggest that this may be a case of solving
the wrong problem. Rather than looking for a cheaper distance metric,
you should be looking for a cheaper way to do A*. Or even a cheaper
way to do "chase and follow the player", which may not need A*.

There are ways to optimize A* that allow you to do it without big
CPU hits.

You can divide the dungeon into "segments" (each room a segment;
each hallway chunk without branches or doors a segment) and run
A* on the basis of segment traversal rather than square traversal
for an order of magnitude or more of speed.

You can cache A* results for monsters in the same origin segment
to use when going to the same destination segment. This will get
you another two orders of magnitude (or more, the longer the map
is in use).

Or you can do effective pathfinding without A*. If you accept
that some monsters are sorta dumb and won't do absolutely
perfect pathfinding, you can give them pretty darn good
pathfinding that's O(1). Here's how. When checking the
player's line-of-sight you can calculate a "gradient" score
(something like 32x the turn number minus the distance from
which the square is seen by the player) and store it on the
square. That allows a monster to look at just its surrounding
squares and pick the one with the greatest gradient score
to go into, the effect being that the monster very convincingly
and effectively (though not perfectly like A*) chases the player.

Stop thinking previous gen :P
Start thinking about a world that is not centered around a single character
and where actors need to find paths completely unrelated to the PC. Oh, and
start thinking dynamic maps instead of static ones. One could still
recalculate segments all the time but the whole segment stuff would only add
a lot of complexity. I prefer a clean, general solution to map dependent
hackery.




.

Relevant Pages

  • Re: distance approximation in 3D
    ... You can divide the dungeon into "segments" (each room a segment; ... A* on the basis of segment traversal rather than square traversal ... You can cache A* results for monsters in the same origin segment ... Or you can do effective pathfinding without A*. ...
    (rec.games.roguelike.development)
  • Re: Thoughts concerning map compression
    ... If the game world is only slightly modifiable, the map generation is ... really functional if the map generator is very fast, ... If each map segment was stored as a 100x100 tile segment, ...
    (rec.games.roguelike.development)
  • Re: [PATCH] [request for inclusion] Realtime LSM
    ... > segment and move your stack pointer into a second segment. ... > Or, going the other way, the client app can pass map handles to the ... look at the realtime LSM patch, ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: Nets on a Sphere
    ... Lee Rudolph wrote: ... consider S^2 with its riemannian geometry. ... say of f that "its restriction to each segment of Z" ... should be "a C^1 map which preserves distances", ...
    (sci.math)
  • Re: distance approximation in 3D
    ... by the speed of distance measuring. ... On a big 3D map with many actors this function will be called ... Pathfinding is probably the single most CPU intense task of the entire code ... If ladders are infrequent, a square that is one unit away in the ...
    (rec.games.roguelike.development)