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

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:

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

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

• You can break it down in segments and calculate parts of the way and join them together, if you have the road ABC and DBC, you do not need to recalc BC, just to check if AB or DB is shorter. Don't underestimate calculating power, by the time a player has managed to build a road over 10k tiles, the algorithm has enough time to do the math as well. Don't assume bottlenecks before actually confirming that you have one. Apr 10, 2021 at 15:03
• You also only need to recalculate once the road network changes somehow. So when it does change say by placing a new road, you could spread out this recalculation over several frames and make it on a separate thread. May 10, 2021 at 18:36