- Home /
Simple pathfinding for sector based game
Hi.
I'm currently coding a 2d pure management space game close to the X3: Reunion series but without any graphic.
Meaning by that, the universe is only sectors filled with ships, infrastructures and such. Ships indeed have positioning, but this is abstract, meaning that when they navigate through the sector, it's just a timer before they actually arrive, with no path-finding.
But i need an algorithm for when a ship (player or AI) want to go from one sector to another.
I did a lot of research (maybe not enough but still) and i know about Dijkstra and A* path-finding. But Dijkstra seems outdated and A* use, if i understood it right, coordinates to limit the node it has to cross, for better performance.
In my case, i'm wondering what algorithm would be the best for my very simple use. My ship want to go from sector A to sector B, and it has to find the best route. Of course, if my ship is close to the sector i need, a simple water-flow graph would be enough, just check every neighbor till you find the way, but if sector A is at the opposite side of the galaxy from sector B, it could be slightly costly in term of CPU to go through the whole network again and again. Especially when the player and about 1000 ships will ask the pathfinder for the best route.
A* doesn't seem the best way (or i'm mistaken ? I'm a noob to that), and dijkstra seems the more appropriate. But i want to know if they are other, better ways of doing it.
How games like Master Of Orion handle their path-finding (knowing that since it's turn based, it's less costly that real time like my game)?
Thanks for your answers !
Who said that Dijkstra is outdated? A* doesn't require a grid of coordiantes. You can also use it with nodes. All you need for this is to define the neighboring nodes. Where they are in space is irrelevant. In your case each "grid coordiante" can be represented by an empty which holds a script where you can add empties which can be accessed directly from the current one. And A* if implemented correctly doesn't have a bad impact. In my game I made paths with 30 and more nodes (while A* needed to flood about 500 of them to find the path) and the path was found apparently instantly (I didn't notice any hiccup on the fps). If you work with lists always check if the next element is already in it before doing stuff with it and you'll increase the speed tremendously.
Outdated may be excessive, but most tutorials on pathfinding i thought said that dijkstra was good in the early of game development, then A* came with more optimization, and is now the norm. This is where is saw about the space optimization of A* : https://www.researchgate.net/publication/267405818_Direction_Oriented_Pathfinding_In_Video_Games , that why i wondered if it would be applicable in my case, since the overall direction of my goal sector is irrelevant for my pathfinding issue.
Thanks for the answer, i'll try with A* then.
If A* turns out to slow for a reason you also can try Jump Point Search
Answer by toddisarockstar · Jul 27, 2018 at 05:27 AM
I just finished a custom pathfinding code for a 2d board style game pry similar to yours. its working magically so i thought id share. i have a bunch of territorys. i made a territory class that includes a list of connections to the other territorys.
so of course i make a list of the territory class. now for any given territory number i can know what territories it is connected to.
so in the algo.............. first of all you need an array of ints equal to the amount of territories to store info for at least what territories have been searched and also the amount of steps it took for the algo to get there. i used one array for duel purpose anything bigger than zero in steps tells me that it has allready been looked at.
i also created a basic int called "steps" that counts up every full search loop so we know how to find the path after it is found. i mark this int the above array i mentioned .
fire it up by adding the start territory to a main check list. i am not using a* so i am not using coordinates. i am always working with the zero index when looping through our main list.
so................
enter a while > 0 loop for this main list.
within that loop..........
do a second loop to find all the connections to index 0. if they havent been checked push them in the main list and mark them with the growing steps variable. the steps variable gets one bigger after every full loop of searching.
remember i have a info array equal to the amount of territories for this purpose.
this loop will keep packing info on how many step away it has traveled in this info array.
of course you need a crafty way to break the main loop when it finds the finish territory!
so now that part is done. our main loop is over...................
what i am left with is one array equal to my amount of territorys with numbers representing how many steps from the start. and i have a steps variable that tells me the shortest amount of steps it takes to get there.
so to return my actual path i ripped off the a* concept of tracing backwards. since i allready know the steps i create an array of int equal to steps. then search my connections backwards.
if the steps where 5 for example in a loop i would : look for 4 in the info array based on connections (fill the return array)
look for 3 in the info array based on connections (fill the return array)
look for 2 in the info array based on connections (fill the return array) look for 1 in the info array based on connections (fill the return array) .
.....return my array of territorys .... the end.
this process can be done with any list with a sub list of connections. it could also be expanded upon to include extra data lists for preferences for the path but i thought i give you the basic concept. heres a paste of the funtion that i used for now:
public static int[] PathFind(int start,int finish){
int savefinish = finish; int i,i2;
int steps = 0;string path = "";
if(start!=finish&&start>-1&&finish>-1){
int done = -1;
int[] pinfo = new int[map.list.Count] ;
i = pinfo.Length;
while(i>0){i--;pinfo[i]=-5;}
List<int> check = new List<int>();
List<int> check2 = new List<int>();
check.Add (start);
//--------------------------------------------------------------------------
while(steps<1000&&done<0){
i = check.Count;
while(i>0){i--;
i2 = map.list[check[i]].Connect.Count;
while(i2>0){i2--;
if(pinfo[map.list[check[i]].Connect[i2]]==-5){
pinfo [map.list[check[i]].Connect[i2]] = steps;
if(map.list[check[i]].Connect[i2]==finish){
done = steps;i = 0;i2 = 0;}else{
check2.Add(map.list[check[i]].Connect[i2]);}}}}
steps++;
check = new List<int>();
i = check2.Count;
while(i>0){i--;
check.Add(check2[i]);
}}
path = ""+finish;
if(steps>1){ steps--;
while(steps>0){steps--;
i = map.list[finish].Connect.Count;
List<int> cn = new List<int>();
while(i>0){i--;
if(pinfo[map.list[finish].Connect[i]] == steps){
cn.Add(map.list[finish].Connect[i]);
}}
finish=cn[0];
if(cn.Count>1){
i = cn.Count;
int di = -1;
while (i>0){i--;
i2 = Todd.DistanceReal(new Two(map.list[cn[i]].center.x,
map.list[cn[i]].center.y),
new Two(map.list[savefinish].center.x,
map.list[savefinish].center.y));
if(di==-1){di=i2;finish = cn[i];}else{
if(i2<di){finish = cn[i];di=i2; }
}
}}
path=finish+","+path;
}}}
string[] sa = path.Split(","[0]);
i = sa.Length;
int[] ret = new int[i];
i = sa.Length;
while (i>0) {i--;
int.TryParse(sa[i],out ret[i]);
}
return ret;}
Well, thank you for the algo ! I'll be sure to try to implement that, or at least use it as inspiration for my own A* implementation. $$anonymous$$aybe i'll try some optimization if i can, i was thinking about using A* directionnal filtering to lower the number of cells to check (you know, since if the sector i need to go is at right of my starting sector, i can't check the path on one side of the map).
Anyway, thanks for the answers :)
Your answer
Follow this Question
Related Questions
Collision Avoidance causes jiggling 2 Answers
A* Pathfinding or NavMesh 1 Answer
Issues with movement in an RTS Game. 0 Answers
RTS Grid and Pathfinding 2 Answers