I'm still working on this one, but it's getting quite better.
I've removed the diagonal movement (between two walls), but now the AI tries to avoid every form of diagonal movement, still working on a better method.
sync on
sync : sync
input "sync rate (0 when unsure): ", s
sync rate s
rem RAIPF
rem Realistic Artificial Intelligence Path Finding
rem The fastest and most realistic path finding routine today :)
cls
print "Setting up maze..."
sync
rem Let's setup a maze
dim Maze(50,50)
rem Let's setup a maze mask for our pathfinding method
dim Maze_mask(50,50)
rem Let's make a Maze_mask buffer, this keeps the original AI mask
dim Maze_mask_buffer(50,50)
rem We will need a array to keep the paths in... It can hold up to an unlimited amount
rem of paths for AIs. But we will use only 2 in this case
type Maze_path_Contents
x as integer
y as integer
endtype
dim Maze_AI_distance(1)
dim Maze_AI_Path(0) as Maze_Path_Contents
rem Randomize the maze
RAIPF_Clear_maze(50, 50)
for a=0 to 700
Maze(rnd(49),rnd(49))=1
next a
rem Make sure 1,1 and 49,49 are empty for our candidates
Maze(1,1)=0
Maze(49,49)=0
rem The idea of this pathfinding is simple
rem Based on human thinking, we'll let the AI player discover the maze instead of
rem calculating the path directly to the player.
rem See it as a police raid, they don't know where the terrorists are hiding
rem So they will search the map and once every place is examined, they will go for
rem a second round.
rem The AI player is trying to avoid getting shot by the police (enemy). He knows the way around
rem The AI enemy wants to kill AI player, but isn't familiar with the enviroment...
rem That's why we will use maze_mask()
AI_one_x = 1
AI_one_y = 1
AI_one_state = 0
AI_one_waypoint = 0
AI_two_x = 49
AI_two_y = 49
AI_two_state = 0
AI_two_waypoint = 0
one_thought$ = "I don't know this place"
print "Setting up is done"
print ""
print "--------------------------------------Map legend"
print "Blue box: Wall that is known to the AI"
print "Blue circle: Wall that's still unknown to the AI"
print "Red circle: AI player 1"
print "Green circle: AI player 2"
print "Whenever a AI player sees a wall (range < 3 dots)"
print "it's turned into a blue box"
print "Orange circle: This is where AI 1 wants to go, but if he get's stuck he will go somewhere else"
print ""
print "Press 1 for AI 1 chase example"
print "Press 2 for Random chaos"
c = 0
while c <> 1 and c <> 2
c = val(inkey$())
sync
endwhile
sync
wait key
do
cls
rem Draw the maze
ink rgb(0,0,255),0
for a=0 to 50
for b=0 to 50
if Maze(a,b)=1 and Maze_mask_buffer(a,b)=1
box a*8,b*8,8+a*8,8+b*8
endif
if Maze(a,b)=1 and Maze_mask_buffer(a,b)=0
circle a*8+4,b*8+4,3
endif
next b
next a
rem Draw the AI player
ink rgb(0,255,0),0
circle AI_one_x*8+4,AI_one_y*8+4, 2
circle AI_one_x*8+4,AI_one_y*8+4, 3
rem Draw the AI enemy
ink rgb(255,0,0),0
circle AI_two_x*8+4,AI_two_y*8+4, 2
circle AI_two_x*8+4,AI_two_y*8+4, 3
rem Calculate the next move for the players
if AI_one_state = 0
AI_one_state = 1
new_x = rnd(49)
new_y = rnd(49)
while Maze(new_x, new_y)=1
new_x = rnd(49)
new_y = rnd(49)
endwhile
time = timer()
RAIPF_Calculate_path(AI_one_x, AI_one_y, new_x, new_y, 0)
inc amm
tm = timer()-time
endif
rem Move the player!
if AI_one_state = 1
rem Put new walls inside buffer mask
for a=0 to 2
for b=0 to 2
Maze_mask_buffer(AI_one_x + a - 1, AI_one_y + b - 1) = Maze(AI_one_x + a - 1, AI_one_y + b - 1)
next b
next a
if AI_one_waypoint = Maze_AI_Distance(0)
AI_one_state = 0
AI_one_waypoint = 0
else
if maze(Maze_AI_Path(AI_one_waypoint).x, Maze_AI_Path(AI_one_waypoint).y)=0
AI_one_x = Maze_AI_Path(AI_one_waypoint).x
AI_one_y = Maze_AI_Path(AI_one_waypoint).y
inc AI_one_waypoint
text 425,45,"Array: "+str$(array count(Maze_AI_Path()))
else
AI_one_state = 0
endif
endif
endif
rem Calculate the next move for the players
if AI_two_state = 0
AI_two_state = 1
if c = 2 then new_x = rnd(49)
if c = 2 then new_y = rnd(49)
if c = 1 then new_x = AI_one_x
if c = 1 then new_y = AI_one_y
while Maze(new_x, new_y)=1
new_x = rnd(49)
new_y = rnd(49)
endwhile
time = timer()
RAIPF_Calculate_path(AI_two_x, AI_two_y, new_x, new_y, 1)
inc amm
tm = timer()-time
endif
rem Move the player!
if AI_two_state = 1
rem Put new walls inside buffer mask
for a=0 to 2
for b=0 to 2
Maze_mask_buffer(AI_two_x + a - 1, AI_two_y + b - 1) = Maze(AI_two_x + a - 1, AI_two_y + b - 1)
next b
next a
if AI_two_waypoint = Maze_AI_Distance(1)
AI_two_state = 0
AI_two_waypoint = 0
else
if maze(Maze_AI_Path(Maze_AI_Distance(0)+AI_two_waypoint).x, Maze_AI_Path(Maze_AI_Distance(0)+AI_two_waypoint).y)=0
AI_two_x = Maze_AI_Path(Maze_AI_Distance(0)+AI_two_waypoint).x
AI_two_y = Maze_AI_Path(Maze_AI_Distance(0)+AI_two_waypoint).y
inc AI_two_waypoint
else
AI_two_state = 0
endif
endif
text 425,15,"Time to calculate: "+str$(tm)+"ms"
text 425,50,"Distance 2: "+str$(Maze_AI_Distance(1))
endif
sync
loop
function RAIPF_Calculate_path(x1,y1,x2,y2,slot)
RAIPF_Flip_buffer_to_mask(50,50)
buffer_x = x1
buffer_y = y1
buffer_slot = slot
distance = 0
start_array = 0
incing_x = 1
incing_y = 1
decing_x = 1
decing_y = 1
while buffer_slot > 0
dec buffer_slot
start_array = start_array + Maze_AI_distance(buffer_slot)
endwhile
if Maze_AI_Distance(slot) > 0
for a=1 to Maze_AI_Distance(slot)
array delete element Maze_AI_Path(),start_array
next a
endif
stuck = 0
while (buffer_x <> x2 or buffer_y <> y2) and stuck <> 1
if buffer_x < x2 and incing_x = 1
if Maze_mask(buffer_x+1,buffer_y)=0
inc buffer_x
decing_x = 1
else
if Maze_mask(buffer_x+1,buffer_y-1)=0 and Maze_mask(buffer_x+1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y-1)=0
inc buffer_x
dec buffer_y
incing_y = 1
decing_x = 1
else
if Maze_mask(buffer_x+1,buffer_y+1)=0 and Maze_mask(buffer_x+1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y+1)=0
inc buffer_x
inc buffer_y
decing_y = 1
decing_x = 1
else
incing_x = 0
endif
endif
endif
incing_x = 0
else
if buffer_x > x2 and decing_x = 1
if Maze_mask(buffer_x-1,buffer_y)=0
dec buffer_x
incing_x = 1
else
if Maze_mask(buffer_x-1,buffer_y-1)=0 and Maze_mask(buffer_x-1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y-1)=0
dec buffer_x
dec buffer_y
incing_x = 1
incing_y = 1
else
if Maze_mask(buffer_x-1,buffer_y+1)=0 and Maze_mask(buffer_x-1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y+1)=0
dec buffer_x
inc buffer_y
incing_x = 1
decing_y = 1
else
decing_x = 0
endif
endif
endif
decing_x = 0
else
if buffer_y < y2 and incing_y = 1
if Maze_mask(buffer_x,buffer_y+1)=0
inc buffer_y
decing_y = 1
else
if Maze_mask(buffer_x-1,buffer_y+1)=0 and Maze_mask(buffer_x-1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y+1)=0
dec buffer_x
inc buffer_y
incing_x = 1
decing_y = 1
else
if Maze_mask(buffer_x+1,buffer_y+1)=0 and Maze_mask(buffer_x+1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y+1)=0
inc buffer_x
inc buffer_y
decing_x = 1
decing_y = 1
else
incing_y = 0
endif
endif
endif
incing_y = 0
else
if buffer_y > y2 and decing_y = 1
if Maze_mask(buffer_x,buffer_y-1)=0
dec buffer_y
incing_y = 1
else
if Maze_mask(buffer_x-1,buffer_y-1)=0 and Maze_mask(buffer_x-1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y-1)=0
dec buffer_x
dec buffer_y
incing_x = 1
incing_y = 1
else
if Maze_mask(buffer_x+1,buffer_y-1)=0 and Maze_mask(buffer_x+1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y-1)=0
inc buffer_x
dec buffer_y
decing_x = 1
incing_y = 1
else
decing_y = 0
endif
endif
endif
decing_y = 0
else
rem He needs a little help... just go somewhere :P
if Maze_mask(buffer_x+1,buffer_y)=0
inc buffer_x
else
if Maze_mask(buffer_x-1,buffer_y)=0
dec buffer_x
else
if Maze_mask(buffer_x,buffer_y+1)=0
inc buffer_y
else
if Maze_mask(buffer_x,buffer_y-1)=0
dec buffer_y
else
if Maze_mask(buffer_x-1,buffer_y-1)=0 and Maze_mask(buffer_x-1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y-1)=0
dec buffer_y
dec buffer_x
else
if Maze_mask(buffer_x+1,buffer_y-1)=0 and Maze_mask(buffer_x+1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y-1)=0
dec buffer_y
inc buffer_x
else
if Maze_mask(buffer_x-1,buffer_y+1)=0 and Maze_mask(buffer_x-1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y+1)=0
inc buffer_y
dec buffer_x
else
if Maze_mask(buffer_x+1,buffer_y+1)=0 and Maze_mask(buffer_x+1,buffer_y)=0 and Maze_mask(buffer_x,buffer_y+1)=0
inc buffer_y
inc buffer_x
else
rem SITUATION HOPELESS
stuck = 1
endif
endif
endif
endif
endif
endif
endif
endif
endif
endif
endif
endif
Maze_mask(buffer_x,buffer_y)=1
if Maze_mask(buffer_x+1,buffer_y)=0 then incing_x = 1
if Maze_mask(buffer_x-1,buffer_y)=0 then decing_x = 1
if Maze_mask(buffer_x,buffer_y+1)=0 then incing_y = 1
if Maze_mask(buffer_x,buffer_y-1)=0 then decing_y = 1
if Maze(buffer_x, buffer_y) = 1
buffer_x = x2
buffer_y = y2
else
array insert at element Maze_AI_Path(0), start_array+distance
Maze_AI_Path(start_array + distance).x = buffer_x
Maze_AI_Path(start_array + distance).y = buffer_y
inc distance
endif
endwhile
Maze_AI_distance(slot) = distance
endfunction
function RAIPF_Clear_maze(Maze_size_x, Maze_size_y)
for a=0 to Maze_size_x
for b=0 to Maze_size_y
Maze(a,b)=0
next b
next a
for a=0 to Maze_Size_x
Maze(a,0)=1
Maze(a,Maze_Size_y)=1
next a
for a=0 to Maze_Size_y
Maze(Maze_Size_x,a)=1
Maze(0,a)=1
next a
RAIPF_Clear_maze_buffer(maze_size_x, maze_size_y)
endfunction
function RAIPF_Clear_maze_buffer(Maze_size_x, Maze_size_y)
for a=0 to Maze_size_x
for b=0 to Maze_size_y
Maze_mask_buffer(a,b)=Maze(a,b)
next b
next a
RAIPF_Flip_buffer_to_mask(Maze_size_x, Maze_size_y)
endfunction
function RAIPF_Flip_buffer_to_mask(Maze_size_x, Maze_size_y)
for a=0 to Maze_size_x
for b=0 to Maze_size_y
Maze_mask(a,b)=Maze_mask_buffer(a,b)
next b
next a
endfunction
Here you can see a working example. The final version should allow you to add pathfinding to your game the easy way.
First you need some arrays:
rem Let's setup a maze
dim Maze(50,50)
dim Maze_mask(50,50)
dim Maze_mask_buffer(50,50)
type Maze_path_Contents
x as integer
y as integer
endtype
dim Maze_AI_distance(0)
dim Maze_AI_Path(0) as Maze_Path_Contents
rem Clear all Maze arrays
RAIPF_Clear_maze(50, 50)
Now it's setup for 1 AI ( slot 0 ).
You can calculate a path for him using this code:
new_x = rnd(49)
new_y = rnd(49)
while Maze(new_x, new_y)=1
new_x = rnd(49)
new_y = rnd(49)
endwhile
RAIPF_Calculate_path(old_x, old_y, new_x, new_y, 0)
Now there's a path calculated on the mask_buffer array. Let me explain this:
--- Array --- --- Contains ---
Maze elements useable for your level
Maze_Mask elements used by the AI, his "memory"
Maze_Mask_Buffer elements used by the AI while pathfinding
Let's say this is your level:
XXXX
X
X X
XX X
Dim this:
Dim Maze(6,6)
Dim Maze_Mask(6,6)
Dim Maze_Mask_Buffer(6,6)
Make a border so the AI cannot walk off the map (array errors):
RAIPF_Clear_maze(6, 6)
Now put the level in the maze. You can use map files or data statements, but for now this will do:
maze(1,1)=1 : maze(2,1)=1 : maze(3,1)=1 : maze(4,1)=1
maze(1,2)=1
maze(1,3)=1 : maze(4,3)=1
maze(1,4)=1 : maze(2,4)=1 : maze(4,4)=1
The AI doesn't know this! He thinks there is empty space (only the borders). The pathfinding code calculates the path using the AI's thoughts (buffer_mask).
Now when he moves in this level, you are responsible for making him learn the level.
I used this:
for a=0 to 2
for b=0 to 2
Maze_mask_buffer(AI_one_x + a - 1, AI_one_y + b - 1) = Maze(AI_one_x + a - 1, AI_one_y + b - 1)
next b
next a
The next time you calculate a path, he knows where those walls are and avoids them that time :)
And now you just move him towards the "waypoints"/path stored in the Maze_AI_Path array.
The final version will have better instructions. Tell me what you think
