Re: Pathfinding implementation?
I do have some experience with this, largely using a 2D grid implementation of A star with 8 cardinal directions, optimization can be a bit tricky, especially when scaling or using flocking systems. But part of it can be handled with compartmentalization and sectorization. The implementation used heaps, though Numpy could be another option, with maps that could theoretically scale upwards of 10,000 by 10,000, I was going to further optimize it by breaking down the maps into discrete sector chunks as meta waypoints to reduce load.
For example lets say you have a map thats 320 by 320 tiles, which could take a long time for a pathfinding algorithm to traverse. You take that map and break it into a hundred 32 by 32 Sectors, with each sector containing 1024 tiles. So, if you want an AI to move from one end of the map to another, you first pathfind across the "meta" map of 100 sectors from the AI's current sector to the sector where your destination is, then you pathfind a local path from the AI's current position in the current sector to the next sector along that "meta" path, then caculate another local path through that sector to the next, and so forth and so on. This way your only calculating paths in smaller chunks as you go, the only down side is if you can't reach some adjacent sectors in the sector path because of obsticals in the local sector, like walls for example, but there are ways to optimize around that abit.
Another way you can optimize pathing is to recycle paths when moving in groups, so if Unit A and Unit B are going the same direction, you can share the same pathing data and offset their positions. If you want to get fancy, you could also look into Flow Fields which were used in Supreme Commander 2 and Planetary Annihilation, there's a dev talk [here] about it. Its similar to the picking a set direction and it steering itself towards that goal based on weighted collision data.
As for finding the player, one way could be to implement a search pattern algorithm so they comb the areas systematicallyfor the player, or follow some form of behavior, or you could "cheat" and just pass the players current coordinates either when they spawn or on each cycle so they can home in on them.
-- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
