Please help me figure this out...
Author
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
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.
Author
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
But in any case, thanks a lot. I''ll look into this algorithm.
-Gk2k
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
cyn
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.)
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.
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.
Author
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
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
I''m sure I can get some code done. It will be in Delphi, mind, but I''ll try and post it tomorrow.
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!
There you go. Easy!
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 usableProcedure 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 numberbegin 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 metend;end. There you go. Easy!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
