pacman tile based map problem

The problem here is that you are using the top left coordinates for all the movements. Your collision detection code needs to take into account which direction pacman is moving. For instance, when you are going right, the position you need to check in the can_move_to function is x + pacman_width. It also might be a little more complicated because you need to check all tiles between the Y coordinates of pacman. Something like this, it is in a pseudo code / c code format.


if(MovingRight)
{
bool Solid = false;

//Calculate new position
int New_Pacman_X = Pacman_X + Vel;

//Calculate the X coordinate of the tile the right side of pacman is in (note: it might not have changed from last frame, doesn't matter)
int XTile = (New_Pacman_X + Pacman_Width)/TileSize;

//Calculate the top and bottom Y Coordinates
int TopTile = Pacman_Y / TileSize;
int BottomTile = (Pacman_Y + Pacman_Height) / TileSize;

//Loop from the top and bottom Y coordinates checking to see if any tile is solid
for(int i = TopTile; i <= BottomTile; i++)
{
if(Is_Solid(XTile,i))
Solid = true;
}

//If it is solid, then set the players x to the edge of the tile
if(Solid)
{
Pacman_X = (XTile*Tilesize)-Pacman_Width
}
else
{
//We didn't collide, so we can move pacman to this position
Pacman_X = New_Pacman_X;
}

}

It will have to be done for every direction, but it should solve any collision problems you are having. Also, if this doesn't make sense at first, I encourage you to work out an example on paper and see what this code is actually doing. Also, feel free to ask a question if you don't understand something.

That looks amazingly like this project: http://sourceforge.net/projects/aipac/

If you've derived it from that, have you looked at the movement code that is already included? It behaves quite well for wall collision detection with PacMan moving 8 pixels per step.

-Kirk

That looks amazingly like this project: http://sourceforge.net/projects/aipac/

If you've derived it from that, have you looked at the movement code that is already included? It behaves quite well for wall collision detection with PacMan moving 8 pixels per step.

-Kirk

Hello,
Yes, I am using the tile sets from the project. I haven't looked at the code though.

Hello,
Yes, I am using the tile sets from the project. I haven't looked at the code though.

Excellent. That is my project. 8^) I've just updated it last week to fix some major bugs, in case you're interested. The tiles haven't changed.

PacMan is 32 x 32 while the walls and dots are 16 x 16, so PacMan occupies 4 tiles. The way I do it is to convert PacMan's pixel location into a set of tile coordinates which correspond to the 2D wall or dot map, and check whether there is a wall in that location before moving him. This allows you to move him as fine or coarse grain as you like, as long as you maintain the integrity of the map. For example, moving him 1,2,4,8, or 16 pixels at a time will work, but moving him 3,5,7,9,10,11,12,13,14,15 pixels won't as it'll cause him to bridge through a wall during a move.

I hope that helps a bit.

-Kirk

[quote name='cndl' timestamp='1295280904' post='4760153']
Hello,
Yes, I am using the tile sets from the project. I haven't looked at the code though.

Excellent. That is my project. 8^) I've just updated it last week to fix some major bugs, in case you're interested. The tiles haven't changed.

PacMan is 32 x 32 while the walls and dots are 16 x 16, so PacMan occupies 4 tiles. The way I do it is to convert PacMan's pixel location into a set of tile coordinates which correspond to the 2D wall or dot map, and check whether there is a wall in that location before moving him. This allows you to move him as fine or coarse grain as you like, as long as you maintain the integrity of the map. For example, moving him 1,2,4,8, or 16 pixels at a time will work, but moving him 3,5,7,9,10,11,12,13,14,15 pixels won't as it'll cause him to bridge through a wall during a move.

I hope that helps a bit.

-Kirk
[/quote]

Hehe, awesome. These were the best I found.

The problem here is that you are using the top left coordinates for all the movements. Your collision detection code needs to take into account which direction pacman is moving. For instance, when you are going right, the position you need to check in the can_move_to function is x + pacman_width. It also might be a little more complicated because you need to check all tiles between the Y coordinates of pacman. Something like this, it is in a pseudo code / c code format. [/quote]

I digested through it and I came up with these for the 3 other directions.

LEFT:
newPacX = x - vel
xTile = (newPacX - PacWidth) / TileSize
topTile = y / tileSize
bottomTile = (y + PacHeight) / TileSize

loop i from topTile to bottomTile
solid = true if isSolid(xTile, i)
if solid
x = (xTile * TileSize) + PacHeight
else
x = newPacX

TOP:
newPacY = y - vel
yTile = (newPacY - PacHeight) / TileSize
leftTile =(x / TileSize)
rightTile = (x + PacWidth) / TileSize

loop i from leftTile to rightTile
solid = true if isSolid(i, yTile)
if solid
y = (yTile * TileSize) + PacHeight
else
y = newPacY

BOTTOM:
newPacY = y + vel
yTile = (newPacY + PacHeight) / tileSize
leftTile = (x / TileSize)
rightTile = (x + PacWidth) / tileSize

loop i from lelftTile to rightTile
solid = true if isSolid(i, yTile)
if solid
y = (yTile * TileSize) - PacHeight
else
y = newPacY


But it doesnt seem to work, though. Is it supposed to be 'universal'? Or does the sprite size of character have to be equal to the tile size?

Hehe, awesome. These were the best I found.

That's funny. I made the tiles myself using MS Paint. Thanks! 8^)

But it doesnt seem to work, though. Is it supposed to be 'universal'? Or does the sprite size of character have to be equal to the tile size?
[/quote]


I'm not sure if I'm 100% in agreement on your code. As I see it, you should simply compute the maximum and minimum top/bottom/left/right. It seems you're computing the details too many times. In the code below, I'm assuming what we're trying to find is if there is something in the way (a wall) for the new pacman position. It hasn't been drawn yet, but the Pac's x and y have been updated with the velocity.



//this will define all the tiles that PacMan's space is in contact with

leftTile = newPacX / TileSize
rightTile = (newPacX + PacWidth)/ tileSize
topTile = newPacY / tileSize
bottomTile = (newPacY + PacHeight) / TileSize

solid = false
loop i from topTile to bottomTile
loop j from leftTile to RightTile
solid = true if isSolid(j, i)

if solid
PacMan can't go there

But it doesnt seem to work, though. Is it supposed to be 'universal'? Or does the sprite size of character have to be equal to the tile size?

Do any of the directions work? What actually happens? I can see a couple bugs with the code you posted, here is a fixed version that might work. This is the way I do collision in all my tile based games, mostly platformers, but I've also used it for pacman like games, so the general concept should work.

LEFT:
newPacX = x - vel
xTile = (newPacX) / TileSize
topTile = y / tileSize
bottomTile = (y + PacHeight) / TileSize

loop i from topTile to bottomTile
solid = true if isSolid(xTile, i)
if solid
x = (xTile * TileSize)
else
x = newPacX

TOP:
newPacY = y - vel
yTile = (newPacY) / TileSize
leftTile =(x / TileSize)
rightTile = (x + PacWidth) / TileSize

loop i from leftTile to rightTile
solid = true if isSolid(i, yTile)
if solid
y = (yTile * TileSize)
else
y = newPacY

BOTTOM:
newPacY = y + vel
yTile = (newPacY + PacHeight) / tileSize
leftTile = (x / TileSize)
rightTile = (x + PacWidth) / tileSize

loop i from leftTile to rightTile
solid = true if isSolid(i, yTile)
if solid
y = (yTile * TileSize) - PacHeight
else
y = newPacY

Let me know if this works any better.

[quote name='cndl' timestamp='1295296842' post='4760331']
But it doesnt seem to work, though. Is it supposed to be 'universal'? Or does the sprite size of character have to be equal to the tile size?

Do any of the directions work? What actually happens? I can see a couple bugs with the code you posted, here is a fixed version that might work. This is the way I do collision in all my tile based games, mostly platformers, but I've also used it for pacman like games, so the general concept should work.

LEFT:
newPacX = x - vel
xTile = (newPacX) / TileSize
topTile = y / tileSize
bottomTile = (y + PacHeight) / TileSize

loop i from topTile to bottomTile
solid = true if isSolid(xTile, i)
if solid
x = (xTile * TileSize)
else
x = newPacX

TOP:
newPacY = y - vel
yTile = (newPacY) / TileSize
leftTile =(x / TileSize)
rightTile = (x + PacWidth) / TileSize

loop i from leftTile to rightTile
solid = true if isSolid(i, yTile)
if solid
y = (yTile * TileSize)
else
y = newPacY

BOTTOM:
newPacY = y + vel
yTile = (newPacY + PacHeight) / tileSize
leftTile = (x / TileSize)
rightTile = (x + PacWidth) / tileSize

loop i from leftTile to rightTile
solid = true if isSolid(i, yTile)
if solid
y = (yTile * TileSize) - PacHeight
else
y = newPacY

Let me know if this works any better.
[/quote]

I see where I got the variables wrong.
Although no luck with the updated ones.
He won't move right or bottom. But when I press left or top, he skyrockets in these directions.

Here's my translation:
http://pastie.org/pr...hx4b1ghrzy55dog
I guess I havent made a typo anywhere

I tried by setting pac to 16x16 so that he matches tiles, but that did not change anything.

[quote name='cndl' timestamp='1295296842' post='4760331']
Hehe, awesome. These were the best I found.

That's funny. I made the tiles myself using MS Paint. Thanks! 8^)

But it doesnt seem to work, though. Is it supposed to be 'universal'? Or does the sprite size of character have to be equal to the tile size?
[/quote]


I'm not sure if I'm 100% in agreement on your code. As I see it, you should simply compute the maximum and minimum top/bottom/left/right. It seems you're computing the details too many times. In the code below, I'm assuming what we're trying to find is if there is something in the way (a wall) for the new pacman position. It hasn't been drawn yet, but the Pac's x and y have been updated with the velocity.



//this will define all the tiles that PacMan's space is in contact with

leftTile = newPacX / TileSize
rightTile = (newPacX + PacWidth)/ tileSize
topTile = newPacY / tileSize
bottomTile = (newPacY + PacHeight) / TileSize

solid = false
loop i from topTile to bottomTile
loop j from leftTile to RightTile
solid = true if isSolid(xTile, i)

if solid
PacMan can't go there
[/quote]

Hm, I am not quite sure how to apply this technique.

The nested loop is kinda confusing.

In j0mich01's case I see the pattern that a switch statement is used to group the directions and to do calculations based on them.

Here I am not sure where xTile is comming from (The only explanaition I think would be a switch statement for directions where for (right, left I calculate xTile) and for (top, bottom yTile) am I right?

And for (right, left) directions i'd check isSolid(xTile, i) , for (top, bottom) isSolid(ytile, j). ?

Or I got it totally confused?

Hm, I am not quite sure how to apply this technique.

The nested loop is kinda confusing.

In j0mich01's case I see the pattern that a switch statement is used to group the directions and to do calculations based on them.

For the nested loop, what I've done is to create a box with its left side being the left-most tile, the right side being the right-most tile, top being top-most, and bottom being bottom-most. The nested loop just looks through that entire box of tiles for a wall.

Think of it this way, let's say PacMan's left side is on Tile 9 and his right side is on Tile 10. His top is on Tile 5 and bottom on Tile 6. The nested loop starts on the top row and looks at each column, goes to the next row and then looks at each column again. Like this:

(5,9), (5,10), (6,9), (6,10)

Either mine or jomich's method should work. Mine avoid the need for the switch statement and does a single search over the new desired location.

I think in kirkd's code the xTile is a typo and is supposed to be a 'j'.

I can't see anything wrong with the code you linked, but here is one last thing that might be causing the problem.



def move(side)
solid = false
case side
when :right
nx = @x + @vel
xtile = (nx + PAC_SIZE)/TILE_SIZE
top_tile = @y / TILE_SIZE
bottom_tile = (@y + PAC_SIZE) / TILE_SIZE

if bottom_tile * TILE_SIZE == @y + PAC_SIZE
bottom_tile = bottom_tile - 1

for i in top_tile..bottom_tile
solid = true if @board.solid?(xtile, i)
end

if solid
@x = (xtile * TILE_SIZE) - PAC_SIZE
else
@x = nx
end

when :left
nx = @x - @vel
xtile = nx / TILE_SIZE
top_tile = @y / TILE_SIZE
bottom_tile = (@y + PAC_SIZE) / TILE_SIZE


if bottom_tile * TILE_SIZE == @y + PAC_SIZE
bottom_tile = bottom_tile - 1

for i in top_tile..bottom_tile
solid = true if @board.solid?(xtile, i)
end

if solid
@x = (xtile * TILE_SIZE)
else
@x = nx
end

when :bottom
ny = @y + @vel
ytile = (ny + PAC_SIZE) / TILE_SIZE
left_tile = @x / TILE_SIZE
right_tile = (@x + PAC_SIZE) / TILE_SIZE


if right_tile * TILE_SIZE == @y + PAC_SIZE
right_tile = right_tile - 1

for i in left_tile..right_tile
solid = true if @board.solid?(i, ytile)
end

if solid
@y = (ytile * TILE_SIZE) - PAC_SIZE
else
@y = ny
end

when :top
ny = @y - @vel
ytile = ny / TILE_SIZE
left_tile = @x / TILE_SIZE
right_tile = (@x + PAC_SIZE) / TILE_SIZE


if right_tile * TILE_SIZE == @y + PAC_SIZE
right_tile = right_tile - 1

for i in left_tile..right_tile
solid = true if @board.solid?(i, ytile)
end
if solid
@y = ytile * TILE_SIZE
else
@y = ny
end

end
end


Basically I added lines like this to all the cases (not sure if it is the correct syntax)


if right_tile * TILE_SIZE == @y + PAC_SIZE
right_tile = right_tile - 1

this is needed when pacman is perfectly lined up with an edge or else he will check two tiles instead of one.

Lets say that pacman is 32x32 and each tile is 16x16. lets also say that pacman's position is 16,48 and that he is trying to move up. When you calculate the variables they will be:
assuming @vel = 1

ny = @y - @vel = 48 - 1 = 47
ytile = ny / TILE_SIZE = 47/16 = 2
left_tile = @x / TILE_SIZE = 16/16 = 1
right_tile = (@x + PAC_SIZE) / TILE_SIZE = (16+32)/16 = (48/16) = 3

The problem here is that we now check tile (1,2) (2,2) (3,2). The (3,2) tile shouldn't be checked though because pacman is directly against it. The line of code added to all the cases detects this and fixes it.

I'm not sure if this will make it work, but it is needed.

j0mich01 is absolutely correct. I had a typo in my code, and I have corrected it in the original post.

.
Hi. I managed to get it to work (still not perfect, though). I had to modify your code:

First, I simplified the 'if solid' conditionals

if solid
@y = (ytile * TILE_SIZE) - PAC_SIZE
# these branches here caused him to fly beyond the borders of the map
else
@y = ny
end

I simply used:

@y = ny if !solid
# Update the position only if there's no solid found. Otherwise do nothing



I also found a problem with the code in (top, bottom switch statements):


if right_tile * TILE_SIZE == @y + PAC_SIZE
right_tile -= 1
end
# Turned out that I had to replace @y's with @x's.




Here's the full modified code:
http://pastie.org/pr...gj01zzelon92dfw

For the time being, I made a temporary map with 16x16 tiles and 16x16 box to be absolutely sure that the movement is correct, but there are some spots where the box gets stuck:
Here's a screenshot with some of them:

http://img222.images.../f/pacprob.jpg/

(Red arrows show the path that I am trying to take (but gets stuck), and green ones show the path that succeeds)

As you can notice, when the box gets stuck, it's a tiny bit (like 3 pixels or so) from the wall, so it doesn't fit. I really dont know what is causing it.


With this setup, the underlying solid array is visible nicely, and this made me realise one thing:

http://img64.imagesh...s/i/pacarr.jpg/
(black spots are Walls, Blue spots are movable zone, Yellow big block is pacman as if he was 32x32)

When I do calculations when he's 32x32, I should be using (PAC_SIZE/2) to generate proper tiles for collision detection, as you can see pacman is in fact reaching too far when he is 32x32. (am I right?)

Or should I modify a solid array

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1
0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,1
0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,1
0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,1
0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0

by making the routes (represented by 1) 2 times wider:

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1
0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1
0,1,1,0,0,0,1,1,0,0,0,1,1,0,1,1
0,1,1,0,0,0,1,1,0,0,0,1,1,0,1,1
0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0

That's weird. Changing Pac's size to 15x15 and then removing all the similar checks to 'if right_tile * TILE_SIZE == @x + PAC_SIZE; right_tile -= 1; end' solved it. He doesn't get stuck and he seems to move good by 1 pixel. I will start by experimenting with him as 32x32 (or in this case 31x31)

I think you're doing way too much work here. All you need to do is to compute the new position for PacMan, convert that to tiles, and check whether there is something in any of those tiles. The only piece that is unique for each direction is computing the new position. The rest - converting to tiles, checking for something in those tiles - is universal.

Regarding your code, here's snip with some comments:

when :right
nx = @x + @vel

This is unique to moving right. The remainder should be the same regardless of the direction he's going.


xtile = (nx + PAC_SIZE)/TILE_SIZE

I disagree with this line. I assume @x refers to PacMan's upper left corner, and nx refers to the proposed new upper left corner.
By adding PAC_SIZE, you're shifting to a location that is too far to the right and converting it to a tile. You're actually looking
one tile too far to the right.


top_tile = @y / TILE_SIZE
bottom_tile = (@y + PAC_SIZE) / TILE_SIZE

These look good for this example in which PM is moving right. You have the y-coordinate for top-most tile and the bottom-most tile.



if bottom_tile * TILE_SIZE == @y + PAC_SIZE
bottom_tile -= 1
end

I honestly don't know what this is supposed to be doing.



for i in top_tile..bottom_tile
solid = true if solid?(xtile, i)
end

I think this is OK for this example, but it is only useful for moving right or left. Notice that you actually repeat this type of loop in your code 4 times, one for each direction. Actually, you repeat a number of pieces for each direction that could be captured in on piece - see below.

Here's a modification of your code that I would suggest. I suggest that you continue to think of PacMan as 32x32, as that is what he is.
Since the tiles for the maze are all 16x16, PacMan occupies 4 tile spaces if he is perfectly aligned at the upper left corner of a tile.
If he is shifted a bit, he could occupy as many as 9 tiles with the left and right most tiles being partially occupied.


solid = false
case side
when :right
nx = @x + @vel
ny = @y //Y doesn't change in this case, so go ahead a grab it

when :left
nx = @x - @vel
ny = @y

when :bottom
nx = @x
ny = @y + @vel

when :top
nx = @x
ny = @y - @vel


//define the box that PM will try to occupy by left, right, top and bottom
lefttile = (nx)/TILE_SIZE
righttile = (nx + PAC_SIZE)/TILE_SIZE
top_tile = ny / TILE_SIZE
bottom_tile = (ny + PAC_SIZE) / TILE_SIZE

//use a nested loop to search over all the tiles that PM wants to occupy
for i in top_tile..bottom_tile
for j in left_tile..right_tile
solid = true if solid?(j, i)
end
end

@x = nx if !solid
@y = ny if !solid



Another thing to notice, is that you are using the map for dots (food pellets, coins) for your tiles when you're actually interested in whether he collides with a wall. If you look at the MazeMap.txt file in that code set, you'll see that the corridors are 32 pixels wide and tall - 2 tiles in size to accommodate PM's actual 32x32 size. For that MazeMap, you need to look for a zero to occur in whatever tiles you're checking to tell you it is clear. Anything else is some sort of wall.

I think you're doing way too much work here. All you need to do is to compute the new position for PacMan, convert that to tiles, and check whether there is something in any of those tiles. The only piece that is unique for each direction is computing the new position. The rest - converting to tiles, checking for something in those tiles - is universal.

Regarding your code, here's snip with some comments:

when :right
nx = @x + @vel

This is unique to moving right. The remainder should be the same regardless of the direction he's going.


xtile = (nx + PAC_SIZE)/TILE_SIZE

I disagree with this line. I assume @x refers to PacMan's upper left corner, and nx refers to the proposed new upper left corner.
By adding PAC_SIZE, you're shifting to a location that is too far to the right and converting it to a tile. You're actually looking
one tile too far to the right.


top_tile = @y / TILE_SIZE
bottom_tile = (@y + PAC_SIZE) / TILE_SIZE

These look good for this example in which PM is moving right. You have the y-coordinate for top-most tile and the bottom-most tile.



if bottom_tile * TILE_SIZE == @y + PAC_SIZE
bottom_tile -= 1
end

I honestly don't know what this is supposed to be doing.



for i in top_tile..bottom_tile
solid = true if solid?(xtile, i)
end

I think this is OK for this example, but it is only useful for moving right or left. Notice that you actually repeat this type of loop in your code 4 times, one for each direction. Actually, you repeat a number of pieces for each direction that could be captured in on piece - see below.

Here's a modification of your code that I would suggest. I suggest that you continue to think of PacMan as 32x32, as that is what he is.
Since the tiles for the maze are all 16x16, PacMan occupies 4 tile spaces if he is perfectly aligned at the upper left corner of a tile.
If he is shifted a bit, he could occupy as many as 9 tiles with the left and right most tiles being partially occupied.


solid = false
case side
when :right
nx = @x + @vel
ny = @y //Y doesn't change in this case, so go ahead a grab it

when :left
nx = @x - @vel
ny = @y

when :bottom
nx = @x
ny = @y + @vel

when :top
nx = @x
ny = @y - @vel


//define the box that PM will try to occupy by left, right, top and bottom
lefttile = (nx)/TILE_SIZE
righttile = (nx + PAC_SIZE)/TILE_SIZE
top_tile = ny / TILE_SIZE
bottom_tile = (ny + PAC_SIZE) / TILE_SIZE

//use a nested loop to search over all the tiles that PM wants to occupy
for i in top_tile..bottom_tile
for j in left_tile..right_tile
solid = true if solid?(j, i)
end
end

@x = nx if !solid
@y = ny if !solid



Another thing to notice, is that you are using the map for dots (food pellets, coins) for your tiles when you're actually interested in whether he collides with a wall. If you look at the MazeMap.txt file in that code set, you'll see that the corridors are 32 pixels wide and tall - 2 tiles in size to accommodate PM's actual 32x32 size. For that MazeMap, you need to look for a zero to occur in whatever tiles you're checking to tell you it is clear. Anything else is some sort of wall.

Ah, yes, I knew I had something basic messed up. I used the wrong file to represent the tile array.

Your code is indeed more succint. By default it doesn't work howevever. (He doesn't move, the loop finds too much solids. In the previous code he would get stuck)

But i think I finally found the holy grail. Reducing pacman's size by 1 solved it (For the code you proposed, as well as the previous) I don't exactly know why it did, but it seems a gap of 1 pixel was neccesary.

I will be upgrading him back to the original size, and I will use the MazeMap for walls.

I am sorry that I caused so much trouble, I didn't expect it would last so long.

BUT BIG THANK YOU TO BOTH OF YOU GUYS!!

Not sure why the 1-pixel gap issue arises. None the less, you have something working now. So my code works with this 1-pixel drop in size, too? Hmmm.....

As for trouble, programming is nothing but trouble. 8^)

Good luck on the rest of your project.

-Kirk