Autonomous movement through a tile-based map using collisions?

Physics
#1

Hey folks, 

Hopefully this will be a no-brainer for some of you but I am a stumped regarding an issue with a prototype game I am writing. Let me attempt to explain the problem as well as the desired solution:

The Setup:

I built and displayed a small map using the Dusk engine. It is small and fits entirely on screen so no scrolling or camera movement is required (see attached image).

All the walls are static physics bodies with no bounce factor. The pink rectangle at the top is a dynamic physics body with an initial linear velocity set to move at a velocity of +64 on x and 0 on y, so it’s moving right towards the corner (as the annotated arrows on the image indicate). This rectangle is a non-controlled entity so it’s job is (for the time being), to move autonomously around the map using the walls, and available openings as the bounds for its available movement. The only governing rule in this environment is that the rectangle cannot turn around and go the opposite direction unless the opposite direction is the only available recourse. Otherwise, it must continue moving forward. 

I have a global collision listener setup and am accurately and successfully detecting when the pink rectangle collides with the top right corner (wall) or any wall for that matter. 

The Problem (my interim solution):

Currently, my collision handler is determining the subjects of the collision and in the event that rectangle collides with wall (or corner here), I am treating this like a dead end and then manually determine an alternate available direction using the rectangle’s current location and surrounding tiles. In this case, it would be to move downwards. I then alter the rectangle’s linear velocity to set it in a downward direction. 

Desired Solution:

The good news is that my method works— but I’m not certain this is the optimal way to accomplish this. Ideally, I would like a way to utilize the physics engine in determining the rectangle’s proper course and move around the corner either rotating or reflecting automatically without manual interjection. If you extrapolate this concept around the entire environment, what I would like is that, in any position and any direction on a valid path, the rectangle continue to navigate around while resolving dead ends and/or corners on its own. 

Possible? I am open-minded to any alternative approaches or at least to understand any other options available. I can also post code if necessary or provide more information.

Thanks,

Mike S.

#2

In the old days you would use a 2D array representing the map and your player, enemy, powerup locations as well as empty space.  You would check on each move if the space moving into is occupied by something that blocks your movement.  If so you would allow the object to change direction (left or right or reverse).  If you hit a pick up, remove it and handle the power up.  Hit an enemy, etc.  You could use transitions to move between the squares for smooth movement.

Rob

#3

Ah, so in that case, are you proposing eliminating physics altogether and utilizing traditional transitional movements? The map is already a 2D array. How, then, should I setup the movement engine? Move one tile at a time and evaluate the location? I was sure physics could be used for this.

#4

What physics features do you need?

#5

That’s a good question. Primarily, I like the ability to handle collisions, although I thought it would be great to utilize the physics engine to handle motion of objects. Eventually I will introduce a bullet (for all intents and purposes) I don’t want the overhead of unnecessary movement/decision logic if the existing library can handle it. Also, I require movement to be time-based so I’m not entirely sure how to ensure an object moves a certain number of pixels per second.

Just so I’m clear, you’re proposing that the rectangle- or any moving object- operate using a transition.to - perhaps tile to tile, and then at every point determine what the next move is? 

#6

I’m not proposing anything.  I’m just saying how we did it in the old days without physics.  Many people see that the only official collision detection involves physics so they go down a physics route without really needing it.  I did a space shooter and handled all my blasters without a drop of physics.   Just transitions and checking for collisions using some simple rectangle overlap functions.   If your bullet needs to bounce off things or be affected by gravity, then physics is your friend,  But if the bullet is  just going from point a to point b and you want to know if they hit each other, looks for the tutorial on collision detection without physics.

But if you need to have things that fall (gravity), things that bounce, etc.  Go with physics.

Rob

#7

That does make a lot of sense. It is unlikely that projectile motion will be required.

#8

Shameless plug for my Jumper tutorial, which expands on Roland Yonaba’s grid-based movement logic

http://www.panc.co/tutorials/jumper-logic-modified-for-corona-sdk

#9

Hi Alex! No shame necessary. It’s actually a great suggestion. I’ve already implemented an A* pathfinding routine, but I’m not using it yet. I want to nail down a solid movement policy first. Per your suggestion, I did download Jumper. I’m going to read the documentation and see if I can integrate it.

That said, in the instance where a predetermined path is computed, I’m fairly confident I can work that out. Without a destination, however, I’d love to have an object that accepts a speed and initial direction- then, have it negotiate the map on its own. At most, I’d like to be able to make speed adjustments en-route but not much else. I should probably preface that this is as much a learning experiment for me than actually writing a fully-functioning game. I like to get in the sandbox and get dirty. Admittedly I am looking to emulate the game mechanics of an old and probably lesser-known Atari 2600 title.

#10

In the old days you would use a 2D array representing the map and your player, enemy, powerup locations as well as empty space.  You would check on each move if the space moving into is occupied by something that blocks your movement.  If so you would allow the object to change direction (left or right or reverse).  If you hit a pick up, remove it and handle the power up.  Hit an enemy, etc.  You could use transitions to move between the squares for smooth movement.

Rob

#11

Ah, so in that case, are you proposing eliminating physics altogether and utilizing traditional transitional movements? The map is already a 2D array. How, then, should I setup the movement engine? Move one tile at a time and evaluate the location? I was sure physics could be used for this.

#12

What physics features do you need?

#13

That’s a good question. Primarily, I like the ability to handle collisions, although I thought it would be great to utilize the physics engine to handle motion of objects. Eventually I will introduce a bullet (for all intents and purposes) I don’t want the overhead of unnecessary movement/decision logic if the existing library can handle it. Also, I require movement to be time-based so I’m not entirely sure how to ensure an object moves a certain number of pixels per second.

Just so I’m clear, you’re proposing that the rectangle- or any moving object- operate using a transition.to - perhaps tile to tile, and then at every point determine what the next move is? 

#14

I’m not proposing anything.  I’m just saying how we did it in the old days without physics.  Many people see that the only official collision detection involves physics so they go down a physics route without really needing it.  I did a space shooter and handled all my blasters without a drop of physics.   Just transitions and checking for collisions using some simple rectangle overlap functions.   If your bullet needs to bounce off things or be affected by gravity, then physics is your friend,  But if the bullet is  just going from point a to point b and you want to know if they hit each other, looks for the tutorial on collision detection without physics.

But if you need to have things that fall (gravity), things that bounce, etc.  Go with physics.

Rob

#15

That does make a lot of sense. It is unlikely that projectile motion will be required.

#16

Shameless plug for my Jumper tutorial, which expands on Roland Yonaba’s grid-based movement logic

http://www.panc.co/tutorials/jumper-logic-modified-for-corona-sdk

#17

Hi Alex! No shame necessary. It’s actually a great suggestion. I’ve already implemented an A* pathfinding routine, but I’m not using it yet. I want to nail down a solid movement policy first. Per your suggestion, I did download Jumper. I’m going to read the documentation and see if I can integrate it.

That said, in the instance where a predetermined path is computed, I’m fairly confident I can work that out. Without a destination, however, I’d love to have an object that accepts a speed and initial direction- then, have it negotiate the map on its own. At most, I’d like to be able to make speed adjustments en-route but not much else. I should probably preface that this is as much a learning experiment for me than actually writing a fully-functioning game. I like to get in the sandbox and get dirty. Admittedly I am looking to emulate the game mechanics of an old and probably lesser-known Atari 2600 title.