ogrady
commented
10 years ago Idea for this:
- Use the map as starting-grid
- Remove all solid blocks from the grid -> O(n^2)
- Merge adjacent passable blocks into bigger nodes, until the entity we search the path for can pass through it -> O(n^2)
- Apply some arbitrary pathfinding to this artificial grid -> probably O(n^2)
As we have O(n^2) thrice, it would be nice to store the merged grid for every sort of entity and register them as listeners for the map, to rebuild the grid if needed, instead of building the whole grid each time an entity moves.
When we start implementing NPCs, one obstacle will be that our NPCs are not the same size as one tile of the map. In fact, probably every mech will have his very own size. This might make the use of classic pathfinding dire. Slick2D provides us with pathfinding, to which we maybe can pass those sorts of context-information. http://slick.ninjacave.com/javadoc/org/newdawn/slick/util/pathfinding/package-summary.html If this doesn't work, we might have to span artificial grids for each sort of mech and maintain them whenever the map is manipulated.