Does anyone who dabbles in video game AI know how pathing algorithms usually work? Is it just Dijkstra’s algorithm on a grid? How do you decide priority if two units are both adjacent to a square and you’re moving both of them? In particular, is there a way to figure out in wc3 which units will get through a gap first?
This some advanced stuff. Maybe 1 or two people know this stuff.
Even the classic team may not be able to answer this as it is old code.
My advice would be to look up the dykstra algorithm and then look up AStar those are the most used ones. If you need extra help i might be able to help you tho I don’t have much free time because of game development.
I know Dijkstra/Astar already if I’m given a (non-negatively weighted) digraph, though I’m not sure what the heuristic function would be for Astar here.
Was looking more to understand what the underlying graph would be that you run Dijkstra on in a video game context. Do you make a grid graph, then delete all the nodes/edges with e.g. a building on them? How does unit width (acolyte vs crypt fiend, say) get factored in?
It would be unit collision size. This ilcan be edited easily.
It is the box that is the size of the unit. Frost Wyrms and Abominations have really big collision size making pathing harder.
Riflemen and archers have small collision sizes making movement better
i use an evolution that can store more values per square thus being able to have a grid that has free, temp occupied, occupied by mobile unit and forever occupied.
1 Like
Thanks, this is helpful. Would forever occupied be the places with non destroyable terrain (rocks and such) while temp occupied would be like a wc3 building (that may be destroyed at some point in the future)?
1 Like
yes and units if you want to make a moving unit be able to nudge another unit out of it’s way like in sc2.