Need help with getting A* ai algorithm working with obstacles

[Conal]

Hi I am developing a roguelike in C++ , I use alot of old C ways of doing stuff as Im new to it and just learning as I go, anyway I have a somewhat rough procedural corridors and rooms dungeon. I then went to write A* for my AI as well, anyway as a test I want the mob to take the shortest path to my pc all in one go. This does work to a point in fact if I dont say (if not walkable miss that fcost and dont add to closed list) It always takes the shortest route but thats through walls and everything. If I miss an iteration for obstacles then when the situation arises where there is an obstacle and the mob and PC are on the same height it jams at the wall

 ###
@   #       
      #     M

Fine ^

####
@    #   M
       #

Jams ^     

I have been at the A* for begginers site and have been on this for weeks, I have come to the forums as a last resort.

Heres some theoy pertaining to how Ive immplemented it, in fact heres the code: (Its messy but I am just learning and this is my third immplementation trying to do it through basic arrays also I use -2 as a way to know when I am at the first place I can add an element

Code: [Select]

if(playerturn == true)
{
mobarray[currentm->id] = currentm;
mobarray[currentp->id] = currentp;
//do player turn


//after everything set back to false
playerturn = false;

}else
{


//do mob turn

//look for mob



//find player via current PID
begin_x = currentm->pt.w;
begin_y = currentm->pt.h;




//set player target loc
targetX = currentp->pt.w; //this is where the mob must get to
targetY = currentp->pt.h;

//set mob as start location and start parent
newstartX = begin_x;  //the newstart vars get updated each smallest Fcost
newstartY = begin_y;
parent_x = newstartX;
parent_y = newstartY; //first time before loop parent = newstart
//add the starting square or node to the openlist

theCLOSEDLIST[0][0].cx = newstartX;
theCLOSEDLIST[0][0].cy = newstartY; //it has to be the smallest as its the only item so straight on closed list


//do A*
do
{
targetX = currentp->pt.w; //overkill to make sure target stays current
                targetY = currentp->pt.h;
newstartX  = parent_x;
                newstartY = parent_y;
theCLOSEDLIST[0][0].cx = newstartX; //plan here is to start a new closed list as everything should be renewed at this point
                theCLOSEDLIST[0][0].cy = newstartY;

int smallest = 9999;
int smallesti = -3;
int smallestj = -3;


/**
*
2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.*/
for(int i=0; i<WIDTH; i++)
{
for(int j=0; j<HEIGHT; j++)
{
if(theOLIST[i][j].ox != -2 && theOLIST[i][j].oy != -2 ) //!=-2 means item on list(Openlist)
{

if(theOLIST[i][j].ofcost < smallest && theOLIST[i][j].ofcost > 0  )
{
smallest = theOLIST[i][j].ofcost; //smallest item to openlist
if(theOLIST[i][j].ofcost == smallest  )
{
newstartX= theOLIST[i][j].ox;
newstartY = theOLIST[i][j].oy;
parent_x = newstartX;
parent_y = newstartY; //set new parent to best cost path
}



}



} else
{

}




}

}





/*

c) For each of the 8 squares adjacent to this current square …*/
bool failsquare = false;
bool obs = false;
for(int i=parent_x-1; i<=parent_x+1; i++)
{
for(int j=parent_y-1; j<=parent_y+1; j++) //left sq, middle sq, right sq
{
failsquare = false;
obs=false;




if(j > HEIGHT-1|| i > WIDTH-1)
{
failsquare = true;
}


if(display[i][j].graphic == '#')
{

                    obs = true; //the algo just does not work 100% with obstacles
}

if(failsquare == false && obs == false  )
{


//add to openlist

int gcosttemp =0;



                       
if( j == (parent_y+1) && i == parent_x  || j == (parent_y-1) && i == parent_x || j==parent_y && i== (parent_x+1) || j==parent_y && i==parent_x-1 ) //limited the movements to up down left and right for testing
{
myHC[i][j] = 10*(abs(i - targetX) + abs(j - targetY));
fc = 10*(abs(i - targetX) + abs(j - targetY)); //is this correct? all up down left right gets manhatten run on them?
gcosttemp = 10;
myGC[i][j] = gcosttemp; //code thrashing here :)
//fc = fc+gcosttemp;

fc=fc+gcosttemp; //add gcost onto initial abs

obs = false;

//newstartX =i;
//newstartY =j;




  if(fc < smallest)
  {
  smallest=fc;
  smallesti =i;
  smallestj = j; //at the end of the for loop smallest will = smallest
  }
 
   theOLIST[i][j].ofcost = fc; //trying to add all to the openlist, have tried lots of differtant ways including just putting smallest onto closed list
                                                                                   theOLIST[i][j].ox =i;
theOLIST[i][j].oy =j;
         

bool ditchsucc = false;

obs=false;


} else
{
failsquare = false;
                   
if(obs == true) //theoy was if we are at wall then try to get away from wall, Ive tried just not adding walsl to the openlist but it still fails
{
parent_x = newstartX;
i = parent_x;
parent_y = newstartY+1; //this is wrong. I am just at a loss tbh
j = parent_y;

//if(theOLIST[parent_x][parent_y] ==
}


obs=false; //reset obs to false so next iteration will go ahead




}



               
}
}



//add smallest x y to closedList x y
for(int i=0; i<WIDTH; i++)
{
for(int j=0; j<HEIGHT; j++)
{
if(theCLOSEDLIST[i][j].cx == -2 && theCLOSEDLIST[i][j].cy == -2)
{
if(theOLIST[i][j].ogcost < theCLOSEDLIST[i][j].cgcost)
{
theCLOSEDLIST[i][j].cgcost = theOLIST[i][j].ogcost;
theCLOSEDLIST[i][j].cfcost = theOLIST[i][j].ofcost; //not sure if this is needed at this point I read the steps of the web and do what they state to do but it hasnt made any differance
theCLOSEDLIST[i][j].cx = theOLIST[i][j].ox;
theCLOSEDLIST[i][j].cy = theOLIST[i][j].oy;
parent_x = newstartX;
parent_y = newstartY; //assign a new parent, the plan is it should fcost all aound it again but its like when it gets blocked it wont backtrack because the fcost would be more this is whats happening I believe
}else if(theOLIST[i][j].ogcost > theCLOSEDLIST[i][j].cgcost)
{

}else
{

                           
theCLOSEDLIST[i][j].cx = newstartX;
theCLOSEDLIST[i][j].cy = newstartY;
theCLOSEDLIST[i][j].cgcost = myGC[i][j];
theCLOSEDLIST[i][j].cfcost = smallest;

parent_x = newstartX;
parent_y = newstartY;

}

display[theCLOSEDLIST[i][j].cx][theCLOSEDLIST[i][j].cy].graphic='p';
this->ShowScreen(stdo);//a temporary measure so I can see the path the ai would follow and most times it does get there which is the frustrating thing


                               


i = WIDTH;
j = HEIGHT;


}


}

}
}

/*
If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.           

If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you:

Add the target square to the closed list, in which case the path has been found (see note below), or
Fail to find the target square, and the open list is empty. In this case, there is no path.
**/



}while(parent_x != targetX || parent_y != targetY );

Im using visual studio 2008 as my ide if thats makes any odds and Im really needing some theory or practical tips about the point where manhatten distances get added and when obstacles become a factor

Note I have looked most places on the web and the source I have uses a binary heap, I do not want to use anything fancy I want to stick with basic arays so I can understand whats happening

Thanks
Conal

[Z]

I don't understand why you need this at all. If there is no wall between the monster and PC, then there is no problem. If there is a wall, then the monster should not know where the PC is, so why should it use a pathfinding algorithm?

Also, you might start with some simpler algorithm first (e.g. BFS, Breadth First Search, which should be easy to implement) and then replace it with A*, Dijkstra, or something tailored to your situation (e.g. if all you want to have is shortest paths to PC, the solution is to use Dijkstra algorithm once per PC movement, it will generate shortest paths from all monsters to the single target) when it is obvious that what you have currently is too slow or not exact.

[Conal]

Its cool I did a partial rewrite and got it working, well lets just say 100% of the time it always gets there and say 96% of the time gets the shortest path. Theres a small glitch and I think its my gcost calculation, so what is gcost exactly is it just a simple count from the current square back to the original startsquare so e.g

<SRC> 0gc  |   1gc   |   2gc   | 3gc | 4gc

As a very simple example?

so say current sqauare was square 3 that would have a gcost of 2? Then we add that to the HCOST which is manhatten distance e.g 1* (abs(x-destX) + (y-destY))

I do know about the breadth first algorithm and after experimenting with this one Im not too worried about using it in future. I want to learn A* inside out.  I may well use breadth first but I like shortest path and want it working as well as possible because I have some unique ideas with it.

In my rl I have the following in  place and its as far as I have ever been with it , however I am confident I will complete something although it wont be winning any awards Its all win though as its for the learning:

basic mob AI - mob always gets to player (Its rough but its start)
a set of player and mob test attributes from which I will simulate some fights with the mobs adding items bit by bit(focus on tank enemy mob vs pc to start with)
a procedurally generated REALLY basic map system where all rooms are square but because of the way its done some dont always turn out that way, was unintentional but I understand exactly why its happening and it works out well so all good
The player can move in all directions and cannot move over a mob
I have detached all mob movements pc and npc from the screen array all together which has its benefits
I altered my code so I use screen handles rather than clear screen which eliminated all flickering (I am pleased with the  result of this part as I just redraw the changed cells)

Ive been advised to use external librarys at certain points but I must stress this is purely for education and I would rather use libs once I have a real  understanding of whats involved to really truely develop a rl from the ground up........I have taken out some pretty tough parts and I am determined at the momment. The key differance this time is I have stuck with my RL until theres a bit life about it, It is so neat seeing some little ai creation working! That has given me major incentive, also I am aware that you do not want to be giving all mobs the ability to shorrtest path to the pc but it will be good for running test fights

My development has went from ardous to fun and I can see why it is stated in one of the RL articles that what can happen is one becomes less of a gamer and more into development

I still have a HEAP to learn but I am not to bad at cutting through the layers of semantics to get to something that works in a basic fashion and I will build on that newbie base , bit by tiny bit.

[Etinarg]

Good luck. Overengineering can be the death of a project, too, though, and usually it's good to use the simplest possible approach. A* seems way overpowered and complex for a roguelike, where a breadth first search or dijkstras algorithm are much simpler to code, understand and bugfix while doing the job about as well.

[Conal]

Both you guys have put your views across in a constructive manner. I have A* working reasonably well so I will keep that function , however I am about to write a breadth first algorithm and see how well that works

[Etinarg]

If you want, you can check out this breadth-first search example that I've made a while ago:
http://www.funkelwerk.de/forum/index.php?topic=245.0

[Vanguard]

So it's working fine now?

[Conal]

Thanks guys!

Also Vanguard, yes and no

It always gets to the destination and actually probably 95% of the time the most effcient route is taken, further more because it is not 100% the player has a chance to escape from, the ai fo but a short time. Now whilst this is desirable I will be rewriting the algorithm until it works as intended.

I know where the problem is and it has just came to me while sitting dunk atm how to fix it

What happens is say there are 2 good paths to the destination but one has an obstacle, yes it correcty avoids the obstacle but then because of the new fcost it realises that the previous path was a better one and jumps back a couple of squares

This has perplexed me for a while so I put pen to paper and I think what I need to do is run all these paths into the openlist which I do! Next once all paths are added check the current path set against other paths to see if there is a better one and ONLY then add it to the closed list. As it stands I add the current nodes t o the close list based solely on gcost and hcost

Hajo, I have been studying your code for about 2 days on and off, it is very clean, not uneccisarly overcomplicated and well written.

I need to learn arraylists in C++ as well as template classes though it seems, I am using old style linked lists and arrays as well as pointers  to structs throuhout my RL

I am away to try immplementing a breadth first AI after googling some purely theoretical stuff and then trying to simulate that with pen to paper.

Thanks for taking the time to respond everyone!

[Vanguard]

I can post my java implementation of A* if you think it'd help.  I don't know if it would or not.  I'm basically not capable of reading code written by anyone else, and I don't know if you're the same way.

[Conal]

Guys I edited out this most recent code as I have made progress I think. I need clarification if I am on the right track to BFS before I do more though in essence my Goblin monster is at say

x,y coords
1,3

and my pc is at coords
3,6

in essence what happens is a path goes from the goblin and veres along the width to the right until it hits the ight boundry so e.g

..................
....................
...................
.gppppppppp    where p is the first width path taken
ppppppppppp   2nd width path taken
ppppppppppp   3rd width path taken
ppp@............   4th and final width path taken stops at player

I have this working so that we have a width only path - any obstacles

what I know need is some further direction pertaining to how to get the monster to use this path in a sensible way, I mean say the PC is only 3 height squares above the monster I wouldnt want the monster going through like 80 width squares when all it needs to do is take 2 steps up.

I think I am just not thinking of it right, with the code example submitted here I gather thats what checkMove must do but I am not quite sure I understand what it is doing in practice, that being said I believe now I must make sure all my path values get read into a stack? and then what get the monster to choose random directions in this path? or find the shortest way within this path? Im not sure how to go about this ?

[Etinarg]

The screen format of this thread makes reading very hard. I'd try to help, but I barely can read anything here.
The quoted code made the message view very wide, and horizontal scrolling for reading lines is awkward.

Discussion would be easier if you could fix it, maybe.

[Fenrir]

I probably couldn't help even if I could read the thread, but I'm just here to tell Conal that he can make characters monospace with the following tags.

Code: [Select]

[tt][/tt]
So:
...........
...........
...........
.gppppppppp   where p is the first width path taken
ppppppppppp   2nd width path taken
ppppppppppp   3rd width path taken
ppp@.......   4th and final width path taken stops at player

I'm not picking on you, it's just handy to know.