whethreads.blogg.se - Shortest starcraft 2 game

A-Star (used by 90+% of games) is ideal for this, as the algorithm handles blocked paths fine.This makes it very cheap and thus, fast, to perform.

Starcraft uses subdivision of cells to reduce top level path finding, and then performs a lower level of pathfinding to trace a path from one cell to the next.

So lets address each point in order, using starcraft as an example:

The pathfinding must take into account that the path may become blocked by other allied units/buildings before the path has been completely walked.

The pathfinding must take into account, units of varying size.

The pathfinding must take into account that a path may not be found (blocked).You have to compute paths for all selected units fast.With RTS pathfinding, your requirements are: I'm doing that game only for learning purposes, so I'd love to do all the stuff by myself. So right now the complexity is about 200k per second for one unit.ĮDIT 2: I'd like to avoid using any pathfinding libraries.

I really have no idea.ĮDIT: Well, I'm not going to have different speeds on different terrain, so basically I can go with a simple BFS (still not sure if A* is better than BFS, both have worst case O(|E|), so is it worth to implement A*? BFS is much quicker to write). How can I solve this problem quicker? Maybe different algorithms or. And even if I somehow reduce it, the units in the selected group would detect each other, which can totally mess up the whole pathfinding. probably too much.īut what about few units? For each of them I have to run this algorithm once again, so for 10 units the complexity would be 5 * 10^7, quite a lot for a second. If I'd want my unit to respond to possible obstacle on the path, I'd have to run the algorithm each time it moves, let's say each second. 262k * log 262k = 5* 10^6 (no log for A*, 20 times less) That's quite a lot. Unfortunately, the found path can be blocked by different unit or a building. Movement is tile-based, I don't want to play with navmesh yet.įirst of all my map is tiled (up to 256x256) For a single unit I could definitely go for something like simple shortest path algorithm (maybe Dijkstra or A*). I am wondering how can I implement pathfinding for a selected group of units. I'm doing my first RTS game (something like WarCraft 2) in own game engine using Monogame for graphics.