Pathfinding - What's most efficient?

ID:151296
 
Sep 19 2011, 6:50 am
I'm currently working on a small tower-defense type game for fun. It features dynamic construction, meaning that players can change the terrain in any way, including blocking the target off entirely.

Currently, I use a two-step algorithm for the enemy's pathfinding. In the first step, an "intermediate" target is located, by taking a random turf that lays between the monster and the final target. In the second step, the monster walks towards this intermediate target using BYOND's walk_to() function, which supposedly takes obstacles into account. These two steps are repeated until the target is reached.

My problem here is with the walk_to() function. The algorithm seems to be unable to pass complex, maze-like paths, and instead the monsters will just move towards the target on a direct path, making it impossible to lure enemies into a complex tunnel system. Even if this worked, monsters consider eachother as immovable obstacles, and once one monster has entered a narrow tunnel, no other monsters will follow.


It's clear at this point that this can not be resolved with BYOND's builtin path-finding. There's a good A* pathfinding library that I've used in the past:
http://www.byond.com/developer/Deadron/PathFinding

However, using it bears one problem. I will have dozens of monsters at a time, possibly even a hundred. I may be mistaken, but I think that calculating complex paths for this many monsters at once will be a heavy load on the CPU, considering it's done in DM and not in C++ like with walk_to().

What do you think is the most efficient way to resolve this?
Sep 19 2011, 7:04 am
Instead of having each monster calculate their own path using A*, why not calculate all possible paths from the beginning, then have them pick at random which they will take. If the player changes the terrain, check to see which paths will work and fix any that won't.

Also, allowing the player to completely wall of the target is pretty broken, unless it is extremely easy for enemies to break down buildings, at which point the fastest path may well be to just crush through everything ANYWAY and all of this is a moot point because they can just blast through in a straight line.
Sep 24 2011, 3:13 am (Edited on Sep 24 2011, 3:22 am)
In response to Robertbanks2
Calculating every possible path on a decently large map is impossible for modern (super)computers.

If you must have all your monsters move at one time, there are quite a few maze solving algorithms that are cheaper than A*. A* specifically finds the -shortest- path. Read up about the wall follower rule.