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?