Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

GrayKnight2k

Please help me figure this out...

This topic is 6175 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, I''m new to Artificial Intelligence. Right now I''m using Visual Basic 6 for my games programming. I have a game in the very early stages that I''ve been working on for some time now. It''s one screen per level, and uses tiles. There are the walkable tiles and the nonwalkable wall tiles. I have a user-controlled player, and an enemy that moves (well, somewhat moves) through the level and goes after the player. There''s no way I can figure it out on my own...The player can move around the level, the walls stop him, and the enemy can initially find out what direction to travel in to get to the player (the walls also stop the enemy). The problem is, the enemy won''t walk around all of the walls to get to the player taking the best route possible. I am in dire need of someone to help me with this (preferably do it for me, just because I can''t fathom how to do it and it would help me a whole lot!), and so I have zipped up a file and am ready to send it to any willing Code Master who thinks they might be able to help me solve this problem. What needs to happen is the enemy must know to walk around the walls and stay on path to the player...If it gets jammed in a corner, or even by just one wall, it needs to know how to walk around it or back out of it (in the corner''s case) and I can''t pull it off. What''s in it for you... 1)Your name will be placed on a very Special Thank You list when my project has been completed (and it will be completed!) 2)You will have the satisfaction of knowing you helped a poor newbie who can''t do AI worth an Irish Jig in winter time..(I''m Irish, don''t ask...) SO there it is. Thanks a lot for your help in advance (and I''ll thank you about a million more times as well) and let the requests for my amazing AI file begin! -Gk2k

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster

Sounds like a job for the A* algorithm. Do a search on it. Use www.google.com. Also search for it here on gamedev.net. It really is the bog-standard path finding algo out there, and is not too difficult to employ.

I really doubt you will get anyone to just up and write it for you. However, if you at least make an attempt at writing your own algorighthm, and ask a question here when you run into a brick wall, you will find plenty of peeps who will help you.

Share this post


Link to post
Share on other sites
Right, thanks. I suppose you''re right. It''s just that I''ve tried so many different things for this AI and for countless hours at that, I thought I''d take a shot at the possiblity of someone doing all my dirty work. =)

But in any case, thanks a lot. I''ll look into this algorithm.

-Gk2k

Share this post


Link to post
Share on other sites
i haven''t learned much about A*, but another easy way to find paths is with a recursive maze traversal algorithm. assuming your tiles are only up/down/left/right and your grid isn''t too huge, the performance factor shouldn''t be too much of a hit. if you don''t know how to implement this, just ask.

cyn

Share this post


Link to post
Share on other sites
Do a search here on Gamedev, and also on search engines like Google. The keyword you want is Pathfinding. Specific algorithms include A* (A Star), BFS (Breadth First Search), and Dijkstra''s algorithm. (Note: a lot of people post on here with ''new'' or ''different'' algorithms... but they are nearly always just one of the ''standard'' ones, just that the writer didn''t know it. For example, Cyn''s suggestion is either Breadth-first search or Depth-first search depending on how you implement the recursion. Breadth-first requires an added data structure such as a queue, I think.)

Share this post


Link to post
Share on other sites
Here''s a simple idea.

I''ve never understood all of those pathfinding things, so you could just cheat a bit. Just make a copy of the enemy and send him around the play area. Whenever he meets a point where he has the option of going down more than 1 route, get him to go down either of them randomly. Keep doing this until he meets the player. Then record how long it took to get there. If after, say 10 squares, he hasn''t met the player, start again. Repeat this process several times. Then, get him to go down the route that took the least time. (If none of the routes met him, make him go in a random direction.)

I''ve made a game already like yours and this works well. It makes the enemy act more randomly, and it is more effective when closer to the player. The other pathfinding ways may result in the enemy moving perfectly, which wouldn''t be much fun for anybody who wanted to play the game - more a form of torture. My way at least gives the player a chance. Go on, try it.

Share this post


Link to post
Share on other sites
Hello all - thanks for so many responses. First thing off, Cyn, I like the sound of your idea (I have no idea where to begin with A*) but I'm not sure how to do the recursive maze traversal algorithm. I'd like to know more about it if you would enlighten me a bit. The game entities only travel up/down/left/right and my grid is 20 squares long by 24 squares high.

MarkyD - That is a really cool idea, I think that would definitely enhance the game play with your way of "cheating" for the enemy's path to the player. Unfortunately I'd have no idea how to implement it.

And Kylotan - thanks for your input on the various different algorithms and advice...I've looked into a lot of different path finding algorithms..I found this page last night that seemed to have everything I needed, however for an individual with my skill level, it was like trying to decipher an ancient dialect of chinese writing with a broken flash light.

Unfortunately my problems still lie in the actual coding aspects. MarkyD's idea sounded easiest to me...I could have an enemy, take a copy of that enemy and have it travel down and to the left, down to the right...but I'd still have troubles figuring out how to save those paths and telling the computer which squares are ok and which ones aren't. Sorry, this is all very confusing for me. =0

I'm keeping up my efforts...

Thanks to all,
-Gk2k

Edited by - GrayKnight2k on August 12, 2001 1:07:54 PM

Share this post


Link to post
Share on other sites
I''m sure I can get some code done. It will be in Delphi, mind, but I''ll try and post it tomorrow.

Share this post


Link to post
Share on other sites
Hi there! It may have taken me a couple of hours to do, but I have (finally) written the code that you want. It could be improved - it’s rather s***ty, actually - but it should do. It’s written in Delphi, but I’ve crammed it full of comments so that (nearly) anyone can follow it. Those not familiar with Delphi should know that text in between curvy brackets ‘{}’ and after double slashes ‘//’ are comments. It’s rather big, though, and I am aware of spelling mistakes, so don’t point them out! Whoops. Anywho, here it is. Enjoy!

  

type
Directions = (none, left, right, up, down);
const
XPlayArea = 10; // The X size of the play area (in this case, 10)

YPlayArea = 10; // The Y size of the play area (in this case, 10)

NumOfTrys = 10; // The number of trys the algorithm does (in this case, 10)

NumOfMoves = 10; // The number of moves that the algorithm goes into (in this case, 10)

var
px : integer; // The x coordinate of the player

py : integer; // The y coordinate of the player

ex : integer; // The x coordinate of the enemy

ey : integer; // The y coordinate of the enemy

Dir : Directions; // The direction of the enemy

Occ : array[1..XPlayArea] of array[1..YPlayArea] of Boolean;
// True or False. True if the square is unusable; False if the square is usable


Procedure Move_Enemy;

var
LeastMoves : Integer; // Keeps a record of the least number of moves it takes to reach the player

NewDir : Directions; // The final direction that the algorithm chooses

TempDir : Directions; // The direction that the algorithm is moving in

PTempDir : Directions; // The previous direction that the algorithm was moving in

StartDir : Directions; // The very first direction that the algorithm chooses

Finished : Boolean; // True if the algorithm has finished; False otherwise

Succeeded : Boolean; // True if the algorithm has found the player; False otherwise


cx : Integer; // The x position of the ''Copy'' of the enemy

cy : Integer; // The y position of the ''Copy'' of the enemy


Left1 : Boolean; // True if the square on the left is available (in the algorithm)

Right1 : Boolean; // True if the square on the right is available (in the algorithm)

Up1 : Boolean; // True if the square above is available (in the algorithm)

Down1 : Boolean; // True if the square below is abailable (in the algorithm)


CurrentTry : Integer; // The current route that is algorithm is working on

CurrentMove : Integer; // The current move that is being studied

CurrentSquare : Integer; // The number of squares the algorithm has covered


Left : Boolean; // True if the square on the left is available

Right : Boolean; // True if the square on the right is available

Up : Boolean; // True if the square above is available

Down : Booelan; // True if the square below is abailable

NumOfRoutes : Integer; // Keeps a record of how many ajacent squares are available


RandomNum : Integer; // The random number


begin

NumOfRoutes:=0; // There are no available routes of the current square

Left:=false; // Initializes...

Right:=false // ...these...

Up:=false; // ...four...

Down:=false; // ...variables


{if the enemy is not in the far left column, and the square on the left is available...}
if (ex > 1) and (Occ[ex-1][ey] = false) then
begin
Left:=true; // ...Set ''Left'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

{if the enemy is not in the far right column, and the square on the right is available...}
if (ey < XPlayArea) and (Occ[ex+1][ey] = false) then
begin
Right:=true; // ...Set ''Right'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

{if the enemy is not in the highest row, and the square above is available...}
if (ex > 1) and (Occ[ex][ey-1] = false) then
begin
Up:=true; // ...Set ''Up'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

{if the enemy is not in the lowest row, and the square below is available...}
if (ey < YPlayArea) and (Occ[ex][ey+1] = false) then
begin
Down:=true; // ...Set ''Down'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

if NumOfRoutes = 1 then // If there is only one route available...

begin
if Left = true then NewDir:=Left; // If the enemy can only go left, make it go left

if Right = true then NewDir:=Right; // If the enemy can only go right, make it go right

if Up = true then NewDir:=Up; // If the enemy can only go up, make it go up

if Down = true then NewDir:=Down; // If the enemy can only go down, make it go down

end;

if NumOfRoutes = 2 then // Tf there are two routes available...

begin
{if the enemy can go left, and didn''t already come from the left, make it go left}
if (Left = true) and (Dir <> Right) then
NewDir:=Left;

{if the enemy can go right, and didn''t already come from the right, make it go right}
if (Right = true) and (Dir <> Left) then
NewDir:=Right;

{if the enemy can go up, and didn''t already come from above, make it go up}
if (Up = true) and (Dir <> Down) then
NewDir:=Up;

{if the enemy can go down, and didn''t already come from below, make it go down}
if (Down = true) and (Dir <> Up) then
NewDir:=Down;
end;

if NumOfRoutes > 2 then // If the enemy has a choice of directions...

begin
NewDir:=None; // The enemy is not ready to go in any direction

LeastMoves:=0; // The ''LeastMoves'' variable is initialized


{Here is the main algorithm, which is used whenever there is a choice of routes available to the enemy}

for CurrentTry:=1 to NumOfTrys do // Attempts to find the player using this Loop

begin

cx:=ex; // The X position of the ''Copy'' is reset to the same as the enemy''s

cy:=ey; // The Y position of the ''Copy'' is reset to the same as the enemy''s

CurrentSquare:=0; // The algorithm has gone over no squares

CurrentMove:=0; // The algorithm has met no multiple routes

StartDir:=None; // There is no starting direction


{A random direction is chosen}

repeat
RandomNum:=Random(4);
if (RandomNum = 0) and (Left = true) then
StartDir:=Left;
if (RandomNum = 1) and (Right = true) then
StartDir:=Right;
if (RandomNum = 2) and (Up = true) then
StartDir:=Up;
if (RandomNum = 3) and (Down = true) then
StartDir:=Down;
until StartDir <> None;
TempDir:=StartDir; // The starting direction is assigned to the tempoary direction


Finished:=false; // The algorithm has not finished


repeat
Inc(CurrentSquare); // Increase the number of squares the algorithm has gone over

if CurrentSquare > 1 then // If this is NOT the first square...

begin // ...choose a direction


{Here, I just copied the code from earlier. But instead of using the variables ''Left'' and stuff, I
used ''Left1''.}


NumOfRoutes:=0; // There are no available routes of the current square

Left1:=false; // Initializes...

Right1:=false // ...these...

Up1:=false; // ...four...

Down1:=false; // ...variables


{if the enemy is not in the far left column, and the square on the left is available...}
if (ex > 1) and (Occ[ex-1][ey] = false) then
begin
Left1:=true; // ...Set ''Left'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

{if the enemy is not in the far right column, and the square on the right is available...}
if (ey < XPlayArea) and (Occ[ex+1][ey] = false) then
begin
Right1:=true; // ...Set ''Right'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

{if the enemy is not in the highest row, and the square above is available...}
if (ex > 1) and (Occ[ex][ey-1] = false) then
begin
Up1:=true; // ...Set ''Up'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

{if the enemy is not in the lowest row, and the square below is available...}
if (ey < YPlayArea) and (Occ[ex][ey+1] = false) then
begin
Down1:=true; // ...Set ''Down'' to TRUE

Inc(NumOfRoutes); // Increases the number of routes

end;

if NumOfRoutes = 1 then // If there is only one route available...

begin
if Left1 = true then TempDir:=Left; // If the Copy can only go left, make it go left

if Right1 = true then TempDir:=Right; // If the Copy can only go right, make it go right

if Up1 = true then TempDir:=Up; // If the Copy can only go up, make it go up

if Down1 = true then TempDir:=Down; // If the Copy can only go down, make it go down

end;

if NumOfRoutes = 2 then
begin
{if the Copy can go left, and didn''t already come from the left, make it go left}
if (Left1 = true) and (PTempDir <> Right) then
TempDir:=Left;

{if the Copy can go right, and didn''t already come from the right, make it go right}
if (Right1 = true) and (PTempDir <> Left) then
TempDir:=Right;

{if the Copy can go up, and didn''t already come from above, make it go up}
if (Up1 = true) and (PTempDir <> Down) then
TempDir:=Up;

{if the Copy can go down, and didn''t already come from below, make it go down}
if (Down1 = true) and (PTempDir <> Up) then
TempDir:=Down;
end;

if NumOfRoutes > 2 then // If the Copy has a choice of directions...

begin
repeat // ...randomly choose a direction

RandomNum:=Random(4);
if (RandomNum = 0) and (Left1 = true) then
TempDir:=Left;
if (RandomNum = 1) and (Right1 = true) then
TempDir:=Right;
if (RandomNum = 2) and (Up1 = true) then
TempDir:=Up;
if (RandomNum = 3) and (Down1 = true) then
TempDir:=Down;
until TempDir <> None;
Inc(CurrentMove); // Increase the number of moves the algorithm has done

if CurrentMove = NumOfMoves then // If the current move = the maximum number of moves...

begin
Finished:=true; // ...then this try has finished...

Succeeded:=false; // ...and failed

end;
end;

{End of copied code}

end;

{Move the Copy of the enemy}
case TempDir of
Left : Dec(ex);
Right : Inc(ex);
Up : Dec(ey);
Down : Inc(ey);
end;

PTempDir:=TempDir; // The tempoary direction is assigned to ''PTempDir''


If (ex = px) and (ey = py) then // If the enemy and the player meet...

begin
Finished:=true; // ...inicate that it is finished...

Succeeded:=true; // ...and that it was successful

end;

until finished;

if (Successful) and (CurrentSquare < LeastMoves) and (LeastMoves > 0) then
begin
LeastMoves:=CurrentSquare;
NewDir:=StartDir;
end;

end; // If ''CurrentTry'' has not met ''NumOfTrys'', execution jumps back.


if NewDir = None then // If the algorithm didn''t find the player...

repeat
RandomNum:=Random(4);
if (RandomNum = 0) and (Left = true) then
NewDir:=Left;
if (RandomNum = 1) and (Right = true) then
NewDir:=Right;
if (RandomNum = 2) and (Up = true) then
NewDir:=Up;
if (RandomNum = 3) and (Down = true) then
NewDir:=Down;
until NewDir <> None;
end;

Dir:=NewDir; // Now that the direction has been found, assign it to the first one


{Move the enemy}
case Dir of
Left : Dec(ex);
Right : Inc(ex);
Up : Dec(ey);
Down : Inc(ey);
end;

if (ex = px) and (ey = py) then // If the enemy and player are both in the same position...

MEET; // ...then they have met


end;

end.



There you go. Easy!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!