How do I make enemies navigate through a maze?
Blitz3D Forums/Blitz3D Beginners Area/How do I make enemies navigate through a maze?
| ||
Hey, I'm working on a 3D game right now(Called Robo Attack:) and need my enemy robots to be able to navigate through a maze, while still chasing the player. I.e, if the player is on one end of the maze, and the robot is on the other, he should take the quickest route to reach the player. I believe this is achieved through creating several pivots, and having the robot run back and forth to those depending on where the player might be, but I have no idea what I'm doing, lol. Could anyone help out with this? Thanks, WALNUT |
| ||
A* (Astar) pathfinding. Probably at least a few examples in the code archives. [edit] http://www.blitzbasic.com/codearcs/codearcs.php?code=2069 |
| ||
Hi about A* a good tutorial with b3d code and nice links: http://www.policyalmanac.org/games/aStarTutorial.htm Juan |
| ||
Ok. Thanks guys! I'll check out the links in a bit. WALNUT |
| ||
This is something I wrote. 3D is much harder, but you could still base it around a 2D grid. WayPointer |
| ||
Oky doke. Ty killer! I think Charrua's will work out nicely though. I took a quick look, and it seems like something I can follow. If not, I'll take a look at yours and GFK's. Thanks again everyone! WERDNA |
| ||
If your maze is divided up into a grid, then you can do the following: Make an array the same size as your grid. Make a list. Add the robot's position to the list. Set Counter to 0. Repeat Increment the counter. For each tile in the list, scan around it for tiles which are adjacent to it, reachable (not blocked by walls), and which do not have a number in them already. Set those tiles to the value of Counter. Until you have reached the player. Then, starting at the player: Record the position. Find the lowest number adjacent to that position which is reachable. Move to that position. Repeat until you have reached the robot. This will give you the shortest path from player to robot. If your game is not based on a grid, then you can still do something like the above, but you're on your own figuring out how to implement it. There's many different ways you could go about it. |
| ||
if I remember correctly werdna, in your game robo attack, walls can be pushed around and destroyed so I would suggest something like a* as apposed to a waypoint system. |
| ||
He he he. That was the old version of Robo Attack. I only did that since I had no idea how to make them navigate the maze. For the new version, the maze is solid, and cannot be pushed or destroyed by ANYONE. Thanks though for pointing that out! I'm using Charrua's suggestion right now by the way. Trying to convert it to 3D sucks, simply because I don't yet have a clue what I'm doing :) I'll figure it out soon enough though. As soon as I get the pathfinding done for the robots, I should be very close to having the next Robo Attack demo ready! (I'll post some screenshots as soon as I get a chance in the Blitz Showcase) Thanks for your help everyone! WERDNA |
| ||
I found A* pathfinding very frustrating when I had a go. I gave up, and decided to get back into it. Second time around it made more sense. In was using only waypoints though, but the same idea is involved. Good luck with this! Stick at it. It will "click" |
| ||
Thanks Ross! I'm finding it very confusing at the moment, but I'm sure I'll figure it out in time. For now I'm just sticking to working on the new level models :) |
| ||
Question: Do these enemies instinctively KNOW where the player character is and attempt to home in/track him down? or Are they simply navigating the maze in what would appear to be a logiccal searching pattern or Are they actively attempting to search through the maze, ensuring that by "coordinating" with each other and their local region of the maze, they perfoem an effective and methodical sweep ? |
| ||
They know where he is. I think thats the best option for this kind of game. |
| ||
:) Maybe make the walls transparent to make it seem as if the robots really do KNOW where you are.. hmmm? Perhaps... maybe? I still haven't figured out AI path finding. But! I did make a Match 3 (or 2, or 5, or 50 or any number) game and in order to do that, I had to see if blocks/tiles of the same type were near it. I just made a loop where you input one tile, and it checks up, down, left, and right and if there is the same block next to it, it selects the block and then performs the loop on it too. |
| ||
When I once modded a 2D A* pathfinding routine to 3D it turned out the whole calculation part became rather slow - too slow for realtime calculation. So today I would use something diffrent. EG. a Waypoint system with crossroads, combined with some kind of real word shipping address system, based on region, crossroad, street and number. The "postman" will then know the best way to the shipping address, probably not always the very best way, but all in all not completely wrong. The routes are precalculated. each house has the best routes to the next crossroads, each crossroad to the surrounding region centers, each region center to all other region centers. Something like that. But this still required to define a lot of waypoints and things. An other approach would be to precalculate the A* stuff. If there are not too many grid points then it might be possible to store all the best ways to any other point for every single point. EG let's say we have 10*10*10 points. Lets say an approximate way consists of about 20 points. that's about 80 Megabyte of ram. When a bank is used, with 16 Bit values or 8 Bit values, then it takes only 40 or 20 megs. |
| ||
Not sure I understand what your saying jfk. The whole A* pathfinding thing is too complex for me right now. I'll come back to it in a month or so though. That usually works for me if I can't figure something out. For now I'm just using a temporary movement system for my game, where the enemies just move straight forward in whatever direction they are facing, and then if they hit a wall, they rotate in a random 45 degree angle direction. And if they are close to the player, they ignore their rotation code and just chase him. It seems to work out ok as a temporary fix until I figure the pathfinding out. Anyways, Thanks again for your help everyone! WERDNA |
| ||
You could place a bunch of waypoints (pivots) around the world (not inside walls) and have the robots go to the nearest waypoint but when they get close enough to the player, they ignore the waypoints. |
| ||
I might not have need of the pathfinding after all, lol. I just play tested my new maze in robo attack, and it is not nearly as fun as the game used to be :( Its funner if I go back to the old method where they can simply destroy the maze walls. So my pathfinding lessons shall be on hold for awhile until I get this sorted out @.@ Thanks anyways though, WERDNA |
| ||
Here's a thought: Have some robots able to destroy walls and others that move faster which can't. |
| ||
some one posted a link about the ins and outs of pacman a few months ago, until i read that i thought ghosts just moved randomly till they saw pac then hit chase mode, but infact they work almost how you described, you can see all the ghosts and all the ghosts can see you (pacman) the thread might have been pacman naked (a disturbing image bested by ms pacman naked o.O) |
| ||
use waypoint :) although im not the best waypoint maker. ull have to fix the code because of this. code: Graphics3D 800, 600, 0, 2 AmbientLight 255,255,255 Dim wp(10) Global cam = CreateCamera() CameraRange cam, 1, 5000 waypoint(cam, wp(0), wp(10)) Global player = CreateCube(cam) Global sky = CreateSphere(100.5) EntityColor sky,102,102,255 ScaleEntity sky, 1000, 1000, 1000 FlipMesh sky Global land = CreatePlane() EntityColor land, 127,127,127 While Not KeyHit(1) If KeyDown(57) MoveEntity cam, 0, 1, 0 MoveEntity cam,0,0,(KeyDown(200)-KeyDown(205))*1 TurnEntity cam,0,(KeyDown(203)-KeyDown(205))*1,0 UpdateWorld RenderWorld Text 10, 10, EntityX(cam) Text 10, 20, EntityY(cam) Text 10, 30, EntityZ(cam) Text 10, 40, EntityX(player) Text 10, 50, EntityY(player) Text 10, 60, EntityZ(player) Flip Wend Function waypoint(entity, point, maxpoints) wp1 = CreateSphere(100.5) For way = 0 To maxpoints wp2 = CopyEntity(wp1) wpy# = 4 PositionEntity wp2, Rnd(1,2), wpy#, Rnd(4,8) PositionEntity entity, EntityX(wp2), wpy#-3, EntityZ(wp2) LabelEntity(cam, wp2, "waypoint"+way) Next End Function Function LabelEntity (camera, entity, label$) If EntityInView (entity, camera) CameraProject camera, EntityX (entity), EntityY (entity), EntityZ (entity) w = StringWidth (label$) h = StringHeight (label$) x = ProjectedX () - (w / 2) - 1 y = ProjectedY () - (h / 2) - 1 Color 0, 0, 0 Rect x, y-40, w + 2, h + 2, 1 Color 255, 255, 255 Text x, y-40, label$ EndIf End Function ~DS~ |
| ||
forget what i said. use this instead: ;move w/ arrowkeys and wsad AppTitle "Waypoint" Graphics3D 800, 600, 0, 2 AmbientLight 255,255,255 Global wpx1# Global wpy1# Global wpz1# Global wpx2# Global wpy2# Global wpz2# Global maxpoints=9 Dim wp(maxpoints) Global cam = CreateCamera() PositionEntity cam, 0,1,0 CameraRange cam, 1, 5000 Global wp1 Global wp2 Global wp3 wp1 = CreateSphere(100.5) wp2 = CreateCube() For way = 0 To maxpoints-1 wp(way) = CopyEntity(wp1) wp3 = CopyEntity(wp2) wpx1# = EntityX(wp(way)) wpz1# = EntityZ(wp(way)) wpx2# = wpx1#+Rnd(10,200) wpy2# = 1 wpz2# = wpz1#+Rnd(40,100) ScaleEntity wp(way), 1,1,1 EntityColor wp(way),68,207,252 ScaleEntity wp3,1,1,1 EntityAlpha wp3,.4 EntityColor wp3,102,200,255 PositionEntity wp(way), wpx2#,wpy2#,wpz2# PositionEntity wp3, EntityX(wp(way)), EntityY(wp(way)), EntityZ(wp(way)) Next Global player = CreateCube(cam) Global sky = CreateSphere(100.5) EntityColor sky,102,102,255 ScaleEntity sky, 500, 500, 500 FlipMesh sky Global land = CreatePlane() EntityColor land, 127,127,127 While Not KeyHit(1) MoveEntity cam,0,0,(KeyDown(200)-KeyDown(208) Or KeyDown(17)-KeyDown(31))*1 TurnEntity cam,0,(KeyDown(203)-KeyDown(205) Or KeyDown(30)-KeyDown(32))*1,0 UpdateWorld RenderWorld For way = 0 To maxpoints-1 LabelEntity2(cam, wp(way), "hi, i'm player "+way+" attached to waypoint"+way) Next If wp3 Then LabelEntity(cam, wp3, "hi, i'm the original player attached to waypoint"+wp3) Text 10, 10, "Instructions: " Text 10, 30, "Go up to the spheres to read what they say!" Flip Wend ;Function waypoint(point1, maxpoints) ;point2 = CopyEntity(point1) ;PositionEntity point2,wpx2#,wpy2#,wpz2# ;Return point2 ;End Function Function LabelEntity (camera, entity, label$) If EntityInView (entity, camera) CameraProject camera, EntityX (entity), EntityY (entity), EntityZ (entity) w = StringWidth (label$) h = StringHeight (label$) x = ProjectedX () - (w / 2) - 1 y = ProjectedY () - (h / 2) - 1 Color 0, 0, 0 Rect x, y-40, w + 2, h + 2, 1 Color 255, 255, 255 Text x, y-40, label$ EndIf End Function Function LabelEntity2 (camera, entity, label$) If EntityInView (entity, camera) CameraProject camera, EntityX (entity), EntityY (entity), EntityZ (entity) w = StringWidth (label$) h = StringHeight (label$) x = ProjectedX () - (w / 2) - 1 y = ProjectedY () - (h / 2) - 40 Color 0, 0, 0 Rect x, y-40, w + 2, h + 2, 1 Color 255, 255, 255 Text x, y-40, label$ EndIf End Function ~DS~ |
| ||
Thanks Shadow Wing! This should work out very nicely! WERDNA |