Pathfinding isn't hard if you have full information and enough memory to store it. Most full info grid pathfinding algorithms, like A-star, are basically variations on flood fill.
I had to develop a new pathfinding algorithm recently.[1] For fun, I've been working on adding NPCs to Second Life. These have to be coded under these constraints:
- Each program is limited to 64KB, for stack, heap, and code. But you can have lots of programs that intercommunicate via messages.
- Finding out about the world is done by ray casting. You get about 100 ray casts per second.
It was interesting to code a maze solver under those constraints. What I wrote is basically "head for goal; if obstructed, wall follow." I do wall following in both directions simultaneously, so the shortest path wins. This finds paths around simple obstacles with minimal time wasted examining cells not of interest. Then, after finding a path, I tighten it up, removing inside corners where possible. This is not absolutely optimal, like A* is, but it's usually pretty good, and requires far fewer ray casts.
The way this comment was initially italicized through so many breaks was truly surprising and took me a few seconds to figure out. By the time I clicked reply you'd already updated it though. For those reading this, it connected everything between the initial A* and the second A* and was jut weird.
I had to develop a new pathfinding algorithm recently.[1] For fun, I've been working on adding NPCs to Second Life. These have to be coded under these constraints:
- Each program is limited to 64KB, for stack, heap, and code. But you can have lots of programs that intercommunicate via messages.
- Finding out about the world is done by ray casting. You get about 100 ray casts per second.
It was interesting to code a maze solver under those constraints. What I wrote is basically "head for goal; if obstructed, wall follow." I do wall following in both directions simultaneously, so the shortest path wins. This finds paths around simple obstacles with minimal time wasted examining cells not of interest. Then, after finding a path, I tighten it up, removing inside corners where possible. This is not absolutely optimal, like A* is, but it's usually pretty good, and requires far fewer ray casts.
[1] https://github.com/John-Nagle/lslutils/blob/master/npc/mazes...