Hello,

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.

Thanks for your answers!

Does it have to be CPU, and have you thought of multithreading it?

Why have pointers to neighbours and not just a 2D array (maybe its for a quad mesh or something)? 

What is the pathing criteria, is it traversing a landscape based on terrain type and slope?

Is this realtime game client or for pregenerating something?

In you last question, you say the root is (0,0). Is that a destination or checkpoint or something?

There was an article here about a year ago on A star and I think it talked about waypoints points to help traverse areas. There are older articles on more generic implementations. Look in https://www.gamedev.net/articles/programming/artificial-intelligence/

1 hour ago, svetpet said:

- 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.

If you have a graph for a 2D tile grid, you could store the nodes in a 2D grid. Then it is a nice simple O(1) to get the node for any given position.

21 hours ago, TeaTreeTim said:

Does it have to be CPU, and have you thought of multithreading it?

Why have pointers to neighbours and not just a 2D array (maybe its for a quad mesh or something)? 

What is the pathing criteria, is it traversing a landscape based on terrain type and slope?

Is this realtime game client or for pregenerating something?

In you last question, you say the root is (0,0). Is that a destination or checkpoint or something?

There was an article here about a year ago on A star and I think it talked about waypoints points to help traverse areas. There are older articles on more generic implementations. Look in https://www.gamedev.net/articles/programming/artificial-intelligence/

 

First to clarify things, I am writing RTS game.

I havent though about being on GPU or multithreaded. Do you have suggestions there? May be using compute shaders and splitting the map on zones? Or running the algorithm in parallel for each unit in the game?

As far as I understand there are two representations - incidence matrix (2d array with positions) or linked list implementation (nodes to neighbours). Is using incidence matrix more efficient in this scenario? Again my concern (regardless of the choice of implementation) will be that the path will be very blocky, because the element in the array will be integer coordinates, not floating point. Is this something to worry about? 

For the pathing criteria - it will be flat terrain with obstacles, similar to Warcraft 3 in terms of trees, buildings and units. 

It is real-time. If we have tree in front of an unit, the unit has to bypass it, but if the tree is cut, the unit can move over it. Same for units that block your path and you have to bypass them.

For the root, I said it in terms of the graph I was thinking to do. If I have to traverse it in order to find my position I have to start from the root node, which for example can be (0,0) position. If I use incidence matrix, though, this problem disappears.

As for waypoints - I am not looking at waypoints system or navmesh system at the moment. I want the movement to be freely available everywhere and if obstacle is destroyed to be able to move through it. May be waypoints+navmesh would be the better choice for this scenario, instead of 2048x2048 2D array. What is your opinion?

CPU multi-threading would be for a pregenerated system, most game clients would be spartan with cpu threads. GPU depends on other AI and physics systems used. A 2D texture that is iteratively rendered is a simple A Star solution. If the AI is in CPU though, you need to get info back and fourth across which can reduce its attractiveness. Also more modern techniques might do something in compute.

A friendly introduction to A star path finding:

https://www.redblobgames.com/pathfinding/a-star/introduction.html

Here are some less generic implementations:

http://aigamedev.com/open/reviews/alienswarm-node-graph/

http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

http://aigamedev.com/open/tutorials/potential-fields/

There are other systems too, with quite a few variations. I don't know how the games you mentioned do their path finding.

I'm going out on a limb here and saying that if someone is asking basic questions about A* and pathfinding in general, the core answer should not be about single- vs. mutli-threaded approaches.

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.

It doesn't matter how Starcraft solved it because they were using generated navmeshes instead of a grid which opens things up completely. They also had enormous time put into things to solve the "300 zergling" problem, pushing blocking units out of the way to avoid artificial chokes, etc. Our OP probably isn't quite there yet if he's simply trying to get a basic A* algo put together.

As for the "diagonal movement" issue, one way of doing it, in layman's terms, is shooting a line from a given node to the next and the next, etc. If that line doesn't hit any obstacles, then you can travel to THAT point in a straight line rather than grid-by-grid. Of course, this is one of the major things that navmesh polys handle inherently since it is guaranteed that you can get from any point along an edge of a poly to any other point on any other edge. (They're created that way.) So what might be a wide open courtyard of 20x20 grid cells could end up being 1 single navmesh poly. 

Thank you all for the answers!!

Definitely cleared a lot of confusion and I will be heading for the navmeshes for the pathfinding. I was looking for the best possible way to handle this problem, not just implement basic A*.

Well, A* is going to be your best pathfinding algo... that's pretty much solved. It's what you are running it on (i.e. grid vs. mesh), what you are doing with it (e.g. including terrain traversal costs), and what you do to deviate from it while you following the path (e.g. steering around dynamic obstacles such as other units) that is going to make the difference.

Since you are new, start with "basic A*" on a grid first. Then figure out how to generate and traverse navmesh polys (there are plenty of resources to autogen those). After that, you can start incrementally screwing with the minutiae.