Path solving for a game with a similiar pathing mechanic to Anno

Question

I cant quite wrap my head around how to solve pathing in my game. The basic premise is you will place buildings and roads on a 2d field and then you will be able to create routes from one building to another where the pathing alghorithm should figure out the shortest path between them (if there is one).

Something to keep in mind is that the game is going to be quazi infinite scale (think factorio) and i cant think of a performant enough solution.

Currently what i am working with is that i have every straight Path segment saved as two (startPoint, endPoint) Vector2Int points in a list. And everytime a new road gets added or some road segment deleted i update this list depending on what happened, example situation:

I have this road

-----|
     |
     |
     |-----
This would be represented in my Roads list as:
0 = startPoint(0, 0) -> endPoint(5, 0)
1 = startPoint(5, 0) -> endPoint(5, 3)
2 = startPoint(5, 3) -> endPoint(10, 3)

I now add another road so we have something like this
-----|
     |
 ----|
     |-----
Which would change the road list to something like:
0 = startPoint(0, 0) -> endPoint(5, 0)
1 = startPoint(5, 0) -> endPoint(5, 2)
2 = startPoint(5, 2) -> endPoint(5, 3)
3 = startPoint(1, 2) -> endPoint(5, 2)
4 = startPoint(5, 3) -> endPoint(10, 3)

What i am doing currently when a new route is to be calculated is that i create a 2d bool array which i am feeding into a A* solver to get the shortest path so the above road gets transformed into:

1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 1

With some starting and endpoint.

This works fine for now but when the player will build on a huge size 10kx10k, i cant imagine generating 10kx10k bool array everytime will be a good solution.

Anybody knows how to optimize this?

Answer 1

The answer is pretty simple, depending on the structure of your game i can think of two possible solutions:

1. Chunking. Since in a theoretical-infinite map you have to load and free parts of the world in order to consume a reasonable amount of memory, you could just chunk the paths too and determine for path-finding the chunks the two points lay in, and (if needed) calculate a line from the two points and identify the chunks this line crosses (so you have the chunks "in between"). After that apply the A* algorithm to the path-points in the identified chunks. This should be fairly easy and the general approach to such games. Of course depending on the complexity of your game you could also just use any path points that are present in the chunks of the currently loaded part of the world.
2. You would need some kind of structure to select path-points by their positions (chunking again would be a solution, but theoretically 2d hashing would work too). After that, imagine a vector connecting start and end point, calculate the center and select any path point in a given radius (depending on how big your "search" radius should be) from that center and apply the A* algorithm. For a big radius you could speed up the calculation by precalculating subgraphs/subsets i.e. grouping connected paths, or identifying bridges which connect other subsets etc.

So basically it boils down to selecting a subset of all path-points for the A* algorithm. Theoretically you could also modify the A* algorithm to work with a infinite set of path points (because of the implemented heuristic assumptions it should find a way, except when there is no way in which case you would stop the algorithm at a given count of iterations)