Anti stack with SolarB's tower defence path-finding

Hey, thanks for checking out my example

Unit overlap has always been the bane of developers, I think I read somewhere that even the Starcraft devs came up with hacky ways of overcoming this and you'll still see unit glitches here and there.

Maybe the best way here is to somehow check if there's a unit already on a tile and to stop the nearest unit(s) from moving there. I'm not sure how this will work and unfortunately I don't have the time to experiment but if anyone has any ideas please share.

Not sure about why enemy movement goes wrong above a certain speed, but I'd guess it relates to your "MoveTimer" variable.

Having said that, I can see how the pathfinding engine as a whole could be made very much more efficient.
Basically, you want a single path array, which is shared by all enemies, and which contains the distance of each map tile from the nearest player. You store the positions of each player, and then flood fill outwards from each one, at the same rate - and store the iteration each time.

So on the first loop, you write a "1" at the position of each player. The next loop, you store a "2" adjacent to those. The next loop, you store a "3" adjacent to each cell with a value of "2" - UNLESS that cell already has a value lower than 3 (but not 0, which would mean "un-visited"), or it's an obstacle. And then you just keep going until you can't go any more!
The trick is to keep an ordered "stack" of cells to visit, to make sure you never visit any cell twice - and for that you can use a list object.

I may try to cobble together a quick example, but I've got quite a lot on today...

You can also expand on this system, by giving map squares "weights". For example, an empty space takes a zombie 1 second to walk through, so it has a weight of "1". An unbreakable wall has a weight of "99999999" (ie. infinity). A breakable door might take 5 seconds to break down (and then another second to walk through), so it would have a weight of 5 + 1 = 6.

Alternatively, for something as dumb as a zombie, you might want to compare the walking distance using the calculated path against the straight line distance - and then if the difference is quite low, the zombie will move intelligently, but if it's greater (more of a complex detour) the zombie will just bang its head against the wall or give up. Personally, I think it's really nice when enemies in games are not just differentiated by stats and special abilities but by their AI behaviour (brave, cowardly, aggressive, passive, intelligent, stupid, work together, communicate, use items, use the environment, etc).

Yes, I've had something like this working before for multiple targets, but only in a squad level turn-based strategy game, so performance was never a serious concern.
After a little experimentation, I've come to the conclusion that for AI that completely searches a map the size of yours (90 x 50), it's simply not feasible to do it in realtime (all in one game loop) without slowdown, so you need to spread the calculations out. The zombies will be slower to react, but slowdown can be eliminated that way. I've also cut down the maximum pathfinding range, which helps a lot - you could always use dumb "obstacle avoidance" for zombies far away from any players. Or you get rid of that part and tweak the other parameters to get the kind of performance you want...

I've made a little example of the pathfinding method (not the actual zombie movement) here:
Please login to see this link.

It's fairly well commented, so shouldn't be too hard to follow

The movement stacking should be straight forward. You just want to have each zombie check its distance from the nearest player (using the pathfinding method), and then move them in order, starting with the one closest to a player (any player - it doesn't matter which) - and don't allow any zombie to move into a square that already contains another zombie.

I just modified my previous example to use an array instead of a list (might be faster?), and took out all the graphics that aren't mine.
Please login to see this link.

I haven't looked into the method you're using very thoroughly, so I'm not sure how different it is.

With the method I'm using, there is a map (array) that stores the distance from every single map tile to whichever player is nearest (except for tiles which either contain obstacles or are in areas sealed off by obstacles, which will have a value of zero). To move from any tile to the nearest player, an enemy simply needs to check the map values for the four tiles directly adjacent to its current position, and move to the one with the lowest value, and then keep repeating every time it reaches a new tile.

Using this method, performance is proportional to map size, but not influenced by the number of enemies - so it's perfect for something like a Tower Defense game, where there is typically a smallish map, but many, many enemies.

In games with fewer enemies and larger, more open maps, it's more efficient to use the A* pathfinding algorithm, which is "directed" and doesn't explore the entire map looking for paths.