On 4/4/2019 at 12:34 PM, svetpet said:
I am starting to implement A star in my game and I want to get your advice before doing so.
Currently I have 2048x2048 map, which I plan to turn into a graph, where each node is coordinate - for example (512,512) and its children are the nodes around it - (513,513),(512,513),(513,512),etc. For the implementation of the graph I am looking at linked list of nodes, where each node contains array of its children.
Each node will have bool whether this coordinate is occupied or not. After I have the graph I will run A* on it to get the shortest path.
So I have some questions:
- Is this the right way to approach this problem?
- Will the movement of units be "blocky"? If an unit has to go in diagonal path to an enemy, will he go directly there in straight line or in some weird way, because my coordinates will not support floating point in the graph?
- How is this problem solved in games like Starcraft? How is it solved for very big maps?
- How can I access graph node directly, instead of traversing the whole graph? If my unit is at (1024,1024) and the root of the graph is (0,0) I dont want to traverse the whole thing, just to get to my unit position.
It sounds like you read a A* algorithm in terms of nodes, and you are trying to literally implement that. Next, you run into all kinds of problems since nodes don't quite fit in the program.
Don't do that. An algorithm is described to be as general as it can, in particular, it does not describe anything that is not needed to the algorithm. If it says "nodes" and "connections to other nodes", it means you need something (anything!) that YOU think is a node. It also needs something (anything!) that YOU think is a connection. In other words, you are fully free to see a position in a grid as node, and see a neighbouring position as connection. If you would be writing a city route planner, you'd say a street is a node, and streets connected by junction are neighbours. The algorithm doesn't care about your choices of node and connection, as long as you respect all the required properties that a node and a connection must have in the algorithm.
A quick rundown of your questions (I am running out of time)
- No, don't build a graph of nodes because an algorithm says so. Define what a 'node' is in your problem instead. I'd say "2d position of the grid element".
- Yes, since you decided that connections only exist for the horizontal and vertical neighbour nodes. In general, A* is ultimately about a set discrete positions where you find the shortest path. The algorithm will always follows paths over nodes. I think you will get quite far by adding the 4 diagonal connections too (with a sqrt(2):1 distance). At 2K x 2K, it may not even be noticeable.
- Don't know how starcraft solved it, there are lots of path-finding algorithms maybe have a look at a few others? Alternatively, just go for A* first, make your game, and at a later stage decide if path-finding needs to be improved. If your map is not lots of flat area, 2k x 2k isn't big. Add many obstacles and narrow passes in it.
- The algorithm doesn't care you you identify a node. You can do anything you like. For real nodes, you could add a map from position to the node. If you use position itself as node (ie the (x,y) tuple), getting the node is as simple as making that tuple.
In short, you can freely add things to the algorithm to make it fit to your problem. Just make sure you have a clean and well-defined mapping between concepts in the algorithm and things in your problem, and it will all be fine.
