Ai for Enemies on Tile Map

Author

169

May 11, 2002 07:11 AM

I''ve done the AI for my Tile Game, it is responcible for control the Enemy Soliders. When its an Enemies turn to move the first thing that happens is the Gamestate gets set to GS_ENEMYCHECK. It is responcible for checking that that enemy is alive. If the enemny is alive, and has some movement points left, it then checks to see how far the Enemy unit is from the players unit. Depending on the distance the Enemy will either Walk towards the enemy by setting the game state to GS_ENEMYMOVE or attack the Player by setting the game state to GS_ENEMYATTACK

      

 case GS_ENEMYCHECK:
		{
		if (Unitarray[iWhichUnit].iHealth >0)
			{

			if (iMovePoints>=3)
				{
				NotControlledFunc(iWhichUnit);
				}
			// Workin out distance from enemy to Marine

			// Formula 	d = sqrt( (x1-x2)^2 + (y1-y2)^2))

			
			double dblDistX = Unitarray[0].ptPosition.x - Unitarray[iWhichUnit].ptPosition.x;
			double dblDistY = Unitarray[0].ptPosition.y - Unitarray[iWhichUnit].ptPosition.y;
			dblDistanceToPlayer = sqrt((dblDistX * dblDistX) + (dblDistY * dblDistY));
			
			if (dblDistanceToPlayer > 6 && dblDistanceToPlayer <= 10 ) //&& dblDistanceToPlayer > 15 )

				{ 
                iGameState=GS_ENEMYMOVE;
				
				}
				
			if (dblDistanceToPlayer > 3 && dblDistanceToPlayer <= 6 )
				{
                if(rand() % 100 > 50)
					{
  					iGameState=GS_ENEMYMOVE;
					
					}
				else 
					{
					iGameState=GS_ENEMYATTACK;
					
					}
				}
			if (dblDistanceToPlayer <=3)
				{
                iGameState=GS_ENEMYATTACK;	
				
				}

			if (dblDistanceToPlayer >10)
				{
				iGameState=GS_STARTTURN;
				
				}
			
			}

else {iGameState=GS_STARTTURN;}

}break;

The Game-State GS_EnemyMove is very simple, it justs works out which direction to move to close in on the Player Unit. I.E. North or maybe SouthWest (whatever) It then calls a function that makes sure that amove in that direction can be made and that the enemy is not going to walk into a tree or move into an area controlled by any other unit.If it cannot move in the direction that was selected by the GS_MOVEENEMY gamestate it will try First to move in the direction to the immediate right(NORTHEAST) of the original direction(North). If cannot move to the right of the original direction it will move to the immediate left(NORTHWEST) of the original direction(NORTH). And if it cannot go to the North, NE or NW it will then try East...and then West and so on.

              
void ValidMoveFunc()
{
	int iMoves[7];
    int iCount=0;
	int iOriginalMove;
	bool bMoveEnemy = false;
	iMoves[0]=1;
	iMoves[1]=7;
	iMoves[2]=2;
	iMoves[3]=6;
	iMoves[4]=3;
	iMoves[5]=4;
	iMoves[6]=5;

	//POINT ptNextMove = TileWalker.TileWalk(Unitarray[iWhichUnit].ptPosition, idMoveUnit);

	iOriginalMove = idMoveUnit;
	
	while((bMoveEnemy==false) && (iCount < 6))
	{
    POINT ptNextMove = TileWalker.TileWalk(Unitarray[iWhichUnit].ptPosition, idMoveUnit);

    if (( mlMap[ptNextMove.x][ptNextMove.y].bControlled == false) && ( mlMap[ptNextMove.x][ptNextMove.y].bTree == false))
		{
		bMoveEnemy = true;
		}
	if (!bMoveEnemy)
		{
		int iDirection = ((iOriginalMove + iMoves[iCount]) % 8);

			char filename[20] = "Validmove2.txt";
			int mode = ios::out;
			fstream fout( filename, mode);
			fout << "Validmove" ;
			fout.close();
			
		
		switch(iDirection)
			{
			case 0:
				{
				idMoveUnit=ISO_NORTH;	
				}break;
			case 1:
				{
				idMoveUnit=ISO_NORTHEAST;	
				}break;
			case 2:
				{
				idMoveUnit=ISO_EAST	;
				}break;
			case 3:
				{
				idMoveUnit=ISO_SOUTHEAST;
				}break;
			case 4:
				{
				idMoveUnit=ISO_SOUTH;	
				}break;
			case 5:
				{
					idMoveUnit=ISO_SOUTHWEST;
				}break;
			case 6:
				{
				idMoveUnit=ISO_WEST;	
				}break;
			case 7:
				{
				idMoveUnit=ISO_NORTHWEST;	
				}break;

			}
			iCount++;

		}
	}
}

Then when it leaves this function a valid move has been selected so the game performs the walk animation and all the relevant positions are updated. When the Enemy goes to attack the player the distance from the enemy to the player is calculated and a chance of an enemy hitting the player is calculated.If the Enemy hits the player 5 is subtracted from the players health score.

              
case GS_ENEMYATTACK://skip this unit for now

			{

			iMovePoints--;

	        int ihealty = Unitarray[iPlayer].iHealth;
            // shoot at player  60% chance, -10% for each tile away? or

			//	whatever you want

			// also, if player crouched, -20% more

			int iDamage=5;
            int nChance = 70 - (10 * dblDistanceToPlayer);
          //  if(strcPlayer.nMovementState ==   CHARACTER_CROUCHING)

		//	{

		//		nChance -= 20;

		//	}

  
            if(rand() % 100 < nChance)
            {
              ihealty = ihealty + 0 - 5; 
			  Unitarray[iPlayer].iHealth = ihealty;
			  lpdsb[0]->Play(0,0,0);
            }

			
        
			if (iMovePoints<=0)
				{
			    ControlFunc();
				iGameState=GS_STARTTURN;
				}
			else { iGameState=GS_ENEMYCHECK; }

//select the next unit



			}break;

If anybody has any suggestions of anything to implement or better bits of code please let me know. I plan to let the enemy crouchdown. So the player has less chance of hitting the Enemy and also let the player crouch etc. [edited by - Woody FX on May 8, 2002 10:46:08 AM]

declspec

126

May 11, 2002 08:13 AM

the move function. first kudos. gratz on pumping out a prototype. now if your serious about making it better. heres an idea.

consider: G being goal, E being Enemy (the thing were moving), X being blocks

   GXXXX X E

E will move one up. right. then next time around it will move one back. then move one up. then move one back. with your code that is.

So how do you fix that. well its a common prob its worth fixing for the _experience_. youll be glad you did cause youll get it again.

A*... or for us a conceptual algo with similiarites otherwsie known as "I kick butt ill make the algo up as i go" Which i recommend. nothing like reinventing the wheel to learn why the wheel is round and not square. or in most cases nothing like making a square wheel to make you appreciate the beauty of a round one.

heres a tut. he gives source code that might be tough to read so ill talk you through it.

http://www.geocities.com/jheyesjones/astar.html

its pretty general. but its also adapatable =) but i wouldnt adapt i would learn.

on to our square wheel.

Basically you just keep trying to move till you get to the goal. without moving. you have all the game logic there at your disposal.

now the data structure we use to keep track of stuff is debatable. im going to say priority_queue for simplicity. but i think i can find lots of room to make it go faster there.

we need two of those. one called "open" one called "closed"

on open we hold squares were still thinking bout. on closed we put squares that were done with.

now we start by adding our start square to a node. then we give it a value in the node by detirmining the distance to the goal. set a "path cost" to 0. then we put the start node in "open" then we kick into the loop.

for the loop we pop off our best node. which is easy cause priority_queue inserts ordered. for that to work though we have to define "operator< (Node& n)" in node to return this->value < n.value; having our best node we form successor nodes. these are nodes that i can get to from this node. we value all those by distance to goal. and increment the path cost. handle the parent pointers etc. now we got data for each potential move we look to see if we have moved to this square via another way before.

consider the above case i gave in source. lets say im at the U shape stuck. thats my node. i generate all my succesor nodes. i only get moving back. now im at the step where i look for matching nodes.

i check both open and closed list for my current position. via overloading operator==(Node& n) to compare location. what would i find? well i was there once. i would find on closed via a search my original start node. Now having that node i compare my new path cost. to the old path cost. Well the start node had a path cost of 0. and my new node has a path cost of 3. so i was there in one search once but i had gotten there with less steps. So i dont want to replace my new path with that one. that would be taking the long way. so i leave that node alone. and garbage my new one as useless.

ok back to where i was in describing the algo. were looking for matching nodes in general having just generated succesors to the best square we had so far. We check both open and closed. if its on either we check to see if ours took less steps. if it did take less steps we replace the DATA by copying into that node on the closed list. why? cuase the childs (succesors) of that one are already on the open list and pointing at that node in memory with their "parent" value. if we replace it we loose that link.

ok now suppose we dont find this node on either open or closed. then we put it on open. err insert it cause our open is ordered by "distance to goal"

now remember our original node that we popped off the list to generate succesors. we move it to closed.

go to top of loop popping off the node closest to goal. when finally we have a successor that is the goal. what then?

we use the parent values to reverse the trip. valla your shortest path that wont have the behavior that i mentioned to start this off.

its really alot easier then it sounds.

Woody FX

Author

169

May 13, 2002 05:55 AM

WWOOOWWWWW i''m all dizzy!!!

So i will make a better movement algorithm... nodes..dont really like them!

Will digest what you said.

Thanks

Woody FX

Author

169

May 13, 2002 06:00 AM

Is there away of doing A* without using lists... i really dont like them (too much prolog has turned me off).

I love arrays.. uuummmmmmm arrays.

thanks brian

Unwise owl

158

May 13, 2002 08:31 AM

You don't have to store the nodes in a linked list if that was what you meant. You can store the nodes in a STL-vector too (dynamic array), but each node will still require a separate structure. The A* is a node-searching algorithm and you can't use it without these nodes.

EDIT: Try this page if you want to learn more about the A* algorithm: http://www-cs-students.stanford.edu/~amitp/gameprog.html It links to lots of useful sites about shortest paths.

[edited by - Unwise owl on May 13, 2002 9:33:46 AM]

declspec

126

May 13, 2002 09:28 AM

the big hurdle with using arrays is you dont know how big the "open" and "closed" list can get. vector is a good middle road. but frankly with just using three insanely simple to learn ops push_front, front, pop_front, isEmpty. atleast seems like an option?

if you didnt want to dig through documentation to code complicated stuff you could do all the above just knowing

list< Node* > open,closed,pending;

where you just inserted any order into open then searched it for the best to pop off each time in N time.

  //pending is a holder its emptyNode* current_best = open.front();open.pop_front();while( ! open.isEmpty() ) {     if(open.front()->path_cost < current_best->path_cost)    {            pending.push_front(current_best);         current_best = open.front();    }else    {       pending.push_front(open.front());    }    open.pop_front();};

at loop return current_best has your best node all your open is on pending cept for current_best. now do the loop again to put it all back on open.

note this is N time inside a search loop when it could be constant with log n insertions. read: ewwww. but its simple. and should get you going with this style. the code that i gave you was just code i used to refresh my memory. it looked overly barque to me.

[edited by - declspec on May 13, 2002 10:29:09 AM]