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();*

_ 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;}*_