Wall following problems.

Monkey Forums/Monkey Beginners/Wall following problems.

Pakz(Posted 2015) [#1]
I spend hours trying to get a feature from a platformer game that I saw on a stream working. It had ai that moved around platforms. I looked up how to do this wall following and did not find a lot of explanations.

One psuedo code I found was this.

if nothing on the left side
  turn to the left 90 degrees
elseif nothing in fron
 move forward
else
turn to the right 90 degrees
end if


I modified the code multiple times and got it to do some kinds of movement around the map but it never really worked like it should.

I hope someone knows this wall following technique and can help me out with it.

This is the wall following code.
	Method update()
		Local y1:Int=y/tileheight
		Local x1:Int=x/tilewidth
		' these variables are used to see if a tile is left of the ai
		' and if a tile is in front of the ai
		Local wallleft:Bool=True
		Local infront:Bool = True		
		Local angle2:Int=angle-90
		If angle2<0 Then angle=270
		Local x2:Float=Cos(angle2)*tilewidth
		Local y2:Float=Sin(angle2)*tileheight
		x2/=tilewidth
		y2/=tileheight
		' see if a tile is left of the ai
		If map[y1+y2][x1+x2] = 0 Then wallleft = False
		x2=Cos(angle)*tilewidth
		y2=Sin(angle)*tileheight
		x2/=tilewidth
		y2/=tileheight
		' see if a tile is infront of te ai
		If map[y1+y2][x1+x2] = 0 Then infront = False
		' this handles the wall following.
		If wallleft = False' if nothing on the left then turn to the left
			angle-=90
		Elseif infront = False 'if nothing in front then move ahead
			x+=Cos(angle)*1
			y+=Sin(angle)*1
		Else ' if nothing is right then turn right
			angle+=90
		End If
		' keep the angle inside the 0-360 position
		If angle<0 Then angle=270
		If angle>360 Then angle=90
	End Method


Here is the complete code that runs.


Here's hoping that someone knows what is wrong :)


muddy_shoes(Posted 2015) [#2]
The pseudo-code is misleading/over-simplified. If you take the case where you move forward into a space where you can turn left in a square grid environment and then turn on the spot you will always end up with a gap on your left again (the space you previously moved from). As stands you're just running those checks every frame so you'll end up with the AI making double turns or spinning on the spot. In order for the algorithm to work you need to turn left, then move into the space and then run the decision test again.

There are a number of other issues with the code and the way you're converting between pixel space and your level grid but that's the main problem with the wall-following itself.


Pakz(Posted 2015) [#3]
I hoped it was a simple thing I did wrong. I wil need to try to expand the code then.

Anyways, it was not really that important for me at this time. I saw it and thought it would be nice if I could make it myself. There was not much I could find with google on the technique. I found no working code yet. One example code on a forum did not work after converting it twice.

Maybe I wil get it working in the future.

With the pixel space and the map coordinates. If you have a way that works better then I would gladly learn about that if it is not to difficult or involves vectors or so. I also tried doing this with for loops and going in to the direction one pixel at a time until I would of reached another map coordinate.

Anyways, Thanks for the help so far.


Pakz(Posted 2015) [#4]
I finally figured out how to get those wall crawling baddies in the game. I went through the steps again and now finally saw how it could work. It did not take long to get working.

It goes like this.
A crawler has 4 possible directions it can go into. We remember the direction we are going into.(1=up-2=right-3=down-4=left)
going to the right means increasing the counter to 2+1 = 3(down)
We do this:
See if the right side is a free and move there;return
of if the forward pos is free and move there;return
of if the left pos is free and move there

This is the crawler class:
Class wallcrawler
	'x and y tilepositions(cells)
	Field x:Float,y:Float
	'nx and ny is next tileposition
	Field nx:Int,ny:Int
	'offset for drawing (smooth movement)
	Field offx:Int,offy:Int
	' direction wallcrawler is goint to
	' 1 = up, 2 = right, 3 = down, 4 = left
	Field direction:Int
	Method New(x:Float,y:Float)
		Self.x = x
		Self.y = y
		Self.nx = x
		Self.ny = y
		'start going right
		Self.direction = 2
	End Method
	Method update()
		If x = nx And y = ny
			Else
			' if not on next position then slowly move there
			If x<nx Then offx+=1
			If x>nx Then offx-=1
			If y<ny Then offy+=1
			If y>ny Then offy-=1
			If offx>tilewidth Then x+=1;offx=0
			If offx<-tilewidth Then x-=1;offx=0
			If offy>tileheight Then y+=1;offy=0
			If offy<-tileheight Then y-=1;offy=0
			Return 
		End If
		' get the next directions
		Local rightd:Int=direction+1
		Local forwardd:Int=direction
		Local leftd:Int=direction-1
		' b sure to stay in legal movement
		If rightd > 4 Then rightd = 1
		If leftd < 1 Then leftd = 4
		' first see if we can go right
		If postaken(rightd) = True
				direction = rightd
				movepos(rightd)
				Return			
		End If
		' then see if we can go forward
		If postaken(forwardd) = True
			direction = forwardd
			movepos(forwardd)
			Return
		End If
		'then see if we can go left
		If postaken(leftd) = True
			direction = leftd
			movepos(leftd)
			Return
		End If
	End Method
	' get next cell position
	Method movepos(d:Int)
		nx = x
		ny = y
		Select d
			Case 1;ny-=1
			Case 2;nx+=1
			Case 3;ny+=1
			Case 4;nx-=1
		End Select
	End Method
	'see if the next possible position if a wall
	Method postaken(d:Int)
		Select d
			Case 1;If map[y-1][x] = 0 Then Return True
			Case 2;If map[y][x+1] = 0 Then Return True
			Case 3;If map[y+1][x] = 0 Then Return True
			Case 4;If map[y][x-1] = 0 Then Return True
		End Select
		Return False
	End Method
	Method draw()
		SetColor 255,0,0
		DrawRect x*tilewidth+offx,y*tileheight+offy,tilewidth,tileheight
	End Method
End Class