Simple pathfinding for sector based game

Questions & Answers
1

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 !

2

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*=-5;}*

List check = new List();
List check2 = new List();

  •  check.Add (start);*

  •  //--------------------------------------------------------------------------*

  •  while(steps<1000&&done<0){*

  •  i = check.Count;*

  •  while(i>0){i--;*

_ i2 = map.list[check*].Connect.Count;_
while(i2>0){i2–;
_ if(pinfo[map.list[check].Connect[i2]]==-5){_
_pinfo [map.list[check].Connect[i2]] = steps;
if(map.list[check].Connect[i2]==finish){
done = steps;i = 0;i2 = 0;}else{
check2.Add(map.list[check].Connect[i2]);}}}}
steps++;
check = new List();
i = check2.Count;
while(i>0){i–;
check.Add(check2);
}}*_

* path = “”+finish;*
* if(steps>1){ steps–;*
* while(steps>0){steps–;*
* i = map.list[finish].Connect.Count;*
* List cn = new List();*
* while(i>0){i–;*
_ if(pinfo[map.list[finish].Connect*] == steps){
cn.Add(map.list[finish].Connect);*_

* }}*
* 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*].center.x,
map.list[cn].center.y),
new Two(map.list[savefinish].center.x,
map.list[savefinish].center.y));*_

_ if(di==-1){di=i2;finish = cn*;}else{
if(i2<di){finish = cn;di=i2; }
}*_

* }}*
* path=finish+“,”+path;*

* }}}*

* string[] sa = path.Split(“,”[0]);*
* i = sa.Length;*
_ int ret = new int*;
i = sa.Length;
while (i>0) {i–;
int.TryParse(sa,out ret);
}
return ret;}*_