How do I make enemies navigate through a maze?

Blitz3D Forums/Blitz3D Beginners Area/How do I make enemies navigate through a maze?

WERDNA(Posted 2009) [#1]
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


GfK(Posted 2009) [#2]
A* (Astar) pathfinding. Probably at least a few examples in the code archives.

[edit]

http://www.blitzbasic.com/codearcs/codearcs.php?code=2069


Charrua(Posted 2009) [#3]
Hi

about A* a good tutorial with b3d code and nice links:
http://www.policyalmanac.org/games/aStarTutorial.htm

Juan


WERDNA(Posted 2009) [#4]
Ok. Thanks guys!

I'll check out the links in a bit.

WALNUT


KillerX(Posted 2009) [#5]
This is something I wrote. 3D is much harder, but you could still base it around a 2D grid.

WayPointer


WERDNA(Posted 2009) [#6]
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


sswift(Posted 2009) [#7]
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.


Nate the Great(Posted 2009) [#8]
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.


WERDNA(Posted 2009) [#9]
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


Ross C(Posted 2009) [#10]
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"


WERDNA(Posted 2009) [#11]
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 :)


_PJ_(Posted 2009) [#12]
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 ?


WERDNA(Posted 2009) [#13]
They know where he is.

I think thats the best option for this kind of game.


GIB3D(Posted 2009) [#14]
:) 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.


jfk EO-11110(Posted 2009) [#15]
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.


WERDNA(Posted 2009) [#16]
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


GIB3D(Posted 2009) [#17]
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.


WERDNA(Posted 2009) [#18]
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


sswift(Posted 2009) [#19]
Here's a thought: Have some robots able to destroy walls and others that move faster which can't.


Ginger Tea(Posted 2009) [#20]
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)


Guy Fawkes(Posted 2009) [#21]
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~


Guy Fawkes(Posted 2009) [#22]
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~


WERDNA(Posted 2009) [#23]
Thanks Shadow Wing!

This should work out very nicely!

WERDNA