A* Algorithm

Before I go on to explain my reason for posting, I’d like give a big thanks to all of the awesome people on the forums! You all have been very helpful and… patient when I’ve needed help. :wink:

Now to business -
One of my projects I’m currently working on, is a game like WiiPlay ‘Tanks’ game - https://www.youtube.com/watch?v=uMqEoZivjnU

I am using LevelHelper and SpriteHelper to create all my sprite-sheets and levels, and I was wondering how to code random enemy movement like that seen in the video?
At first I thought simply coding the enemy tanks to randomly move around within the display would work, but the problem is that the enemy tanks don’t know to avoid running into the obstacles I’ve placed using LH…

What would the most efficient way to achieve enemy behavior like that in the video above?
From what I’ve been reading, it looks like the A* Algorithm is probably my best bet…

-Saer [import]uid: 148623 topic_id: 37290 reply_id: 67290[/import]

I just had a thought - would it make sense to code an enemy tank to roam around within a specified area, say x300-x500 | y0-y300 and then once the player comes within 'bout 100pixels the enemy tank would then start to pursue the player and dodge obstacles via the A* code?
Hope that made sense… :slight_smile: [import]uid: 148623 topic_id: 37290 reply_id: 145520[/import]

If your playfield is grid-based, check out Jumper:

https://github.com/Yonaba/Jumper

Open source and straight Lua so it should work fine with Corona. I haven’t used this version but I played with one of the older ones a while back.

For a game I’m currently working on I have enemies traversing a grid-based play field but I don’t use Jumper or anything else because the movement is supposed to be random, plus, the playfield changes on the fly, so a path from A to B might no longer be available after the enemy starts moving.

So I actually move only one “square” at a time and when the enemy hits that next square it plots the next move. 70% of the time it continues straight if there’s no obstacle. If there is something in the way, or the other 30% of the time, it tries to go left or right (random) and then heads off in that direction.

For a tank-like game as seen in the video, you’re probably going to want A* or similar – I’d check out Jumper and see if that will work for you.

Jay
[import]uid: 9440 topic_id: 37290 reply_id: 145535[/import]

Wow, thank you!
I don’t understand all of the code, but what I do understand I can definitely see its usefulness for many different scenarios.

Grid-based, why didn’t I think of that? :smiley:
I don’t necessarily want the enemy tanks to have a path from pointA to pointB, rather more of a random/aimless roaming type movement like you described.
My levels won’t “change on the fly” so that wouldn’t be an issue, but I will have obstacles - created with LH - and I was wondering if in this chunk of code:
In the jumper.grid module [lua] – Usage Example
– First, set a collision map
local map = {
{0,1,0,1,0},
{0,1,0,1,0},
{0,1,1,1,0},
{0,0,0,0,0},
}
– Value for walkable tiles
local walkable = 0

– Library setup
local Grid = require (“jumper.grid”) – The grid class

– Creates a grid object
local grid = Grid(map)
[/lua]

Does this: [lua] local map = {
{0,1,0,1,0},
{0,1,0,1,0},
{0,1,1,1,0},
{0,0,0,0,0},
} [/lua] represent the grid - in which case if visible it would appear on-screen as a 5/4 grid-size - and the 1s represent the obstacles that must be avoided by either the user-object or enemy?
If so, I take it I would just define the grid points that my obstacles coincide with as a square with a value of 1 and tell the enemy tank to avoid those squares?

-Saer [import]uid: 148623 topic_id: 37290 reply_id: 145544[/import]

http://developer.coronalabs.com/code/pathfinding-module uses grid as well.
And yes the map is the actual map where 0 is walkable and 1 is not. You can specify the height and width of the blocks/squares in your grid.

You can make it so if the player is not within 500 pixels of the enemy tank he just roams around aimlessly. Otherwise if he is, start point is the location of the enemy tank and end location is where the player location is and it updates every few squares or even square. [import]uid: 77199 topic_id: 37290 reply_id: 145545[/import]

Awesome!:smiley:

Would either of you mind making a basic-template of how to match an object’s location to the grid and also how to move an object around the grid?
I understand a fair amount of the code, I am just a bit overwhelmed with all the various files and I am unsure what bits I need and don’t need.

-Saer [import]uid: 148623 topic_id: 37290 reply_id: 145610[/import]

http://developer.coronalabs.com/code/pathfinding-demo

That is a demo that explains and shows you how to use the pathfinding module to move an object around.

I am not familiar with Jumper so can’t really help you there, but I’ve heard great things about it. [import]uid: 77199 topic_id: 37290 reply_id: 145629[/import]

Excellent :slight_smile: [import]uid: 8271 topic_id: 37290 reply_id: 145630[/import]

Thanks, I downloaded the A* github file from the link.

I’ve been experimenting with the code and I’m thinking I’d be better off with the Jumper.grid module over the A*, reason being that I don’t want my enemy tank/s to have a specific destination/goal that they are trying to get to.

@J. A. Whye - you mentioned “I have enemies traversing a grid-based play field but I don’t use Jumper or anything else because the movement is supposed to be random” how did you accomplish that? Because that is what I want to do - again, exactly like the type of random enemy movement in the video.

If I did use the jumper.grid module, how would I achieve the following:

  1. Make a custom grid with a size that covers the entire display - 1s corresponding to obstacles I’ve place via LH and 0s representing the area accessible to the player and enemies.

  2. The ability to translate x/y coordinates into a particular grid square and then using math.random (I assume ) code enemy tanks to roam around strictly confined to the squares with a value of 0 - so as to avoid the obstacles - and also have an option for restricting tank/s to a certain group of squares.

The Jumper files do include some explanations, but they are a little vague for a novice programmer like myself … :\

-Saer [import]uid: 148623 topic_id: 37290 reply_id: 145724[/import]

I just had a thought - would it make sense to code an enemy tank to roam around within a specified area, say x300-x500 | y0-y300 and then once the player comes within 'bout 100pixels the enemy tank would then start to pursue the player and dodge obstacles via the A* code?
Hope that made sense… :slight_smile: [import]uid: 148623 topic_id: 37290 reply_id: 145520[/import]

If your playfield is grid-based, check out Jumper:

https://github.com/Yonaba/Jumper

Open source and straight Lua so it should work fine with Corona. I haven’t used this version but I played with one of the older ones a while back.

For a game I’m currently working on I have enemies traversing a grid-based play field but I don’t use Jumper or anything else because the movement is supposed to be random, plus, the playfield changes on the fly, so a path from A to B might no longer be available after the enemy starts moving.

So I actually move only one “square” at a time and when the enemy hits that next square it plots the next move. 70% of the time it continues straight if there’s no obstacle. If there is something in the way, or the other 30% of the time, it tries to go left or right (random) and then heads off in that direction.

For a tank-like game as seen in the video, you’re probably going to want A* or similar – I’d check out Jumper and see if that will work for you.

Jay
[import]uid: 9440 topic_id: 37290 reply_id: 145535[/import]

Wow, thank you!
I don’t understand all of the code, but what I do understand I can definitely see its usefulness for many different scenarios.

Grid-based, why didn’t I think of that? :smiley:
I don’t necessarily want the enemy tanks to have a path from pointA to pointB, rather more of a random/aimless roaming type movement like you described.
My levels won’t “change on the fly” so that wouldn’t be an issue, but I will have obstacles - created with LH - and I was wondering if in this chunk of code:
In the jumper.grid module [lua] – Usage Example
– First, set a collision map
local map = {
{0,1,0,1,0},
{0,1,0,1,0},
{0,1,1,1,0},
{0,0,0,0,0},
}
– Value for walkable tiles
local walkable = 0

– Library setup
local Grid = require (“jumper.grid”) – The grid class

– Creates a grid object
local grid = Grid(map)
[/lua]

Does this: [lua] local map = {
{0,1,0,1,0},
{0,1,0,1,0},
{0,1,1,1,0},
{0,0,0,0,0},
} [/lua] represent the grid - in which case if visible it would appear on-screen as a 5/4 grid-size - and the 1s represent the obstacles that must be avoided by either the user-object or enemy?
If so, I take it I would just define the grid points that my obstacles coincide with as a square with a value of 1 and tell the enemy tank to avoid those squares?

-Saer [import]uid: 148623 topic_id: 37290 reply_id: 145544[/import]

http://developer.coronalabs.com/code/pathfinding-module uses grid as well.
And yes the map is the actual map where 0 is walkable and 1 is not. You can specify the height and width of the blocks/squares in your grid.

You can make it so if the player is not within 500 pixels of the enemy tank he just roams around aimlessly. Otherwise if he is, start point is the location of the enemy tank and end location is where the player location is and it updates every few squares or even square. [import]uid: 77199 topic_id: 37290 reply_id: 145545[/import]

Awesome!:smiley:

Would either of you mind making a basic-template of how to match an object’s location to the grid and also how to move an object around the grid?
I understand a fair amount of the code, I am just a bit overwhelmed with all the various files and I am unsure what bits I need and don’t need.

-Saer [import]uid: 148623 topic_id: 37290 reply_id: 145610[/import]

http://developer.coronalabs.com/code/pathfinding-demo

That is a demo that explains and shows you how to use the pathfinding module to move an object around.

I am not familiar with Jumper so can’t really help you there, but I’ve heard great things about it. [import]uid: 77199 topic_id: 37290 reply_id: 145629[/import]

Excellent :slight_smile: [import]uid: 8271 topic_id: 37290 reply_id: 145630[/import]

Thanks, I downloaded the A* github file from the link.

I’ve been experimenting with the code and I’m thinking I’d be better off with the Jumper.grid module over the A*, reason being that I don’t want my enemy tank/s to have a specific destination/goal that they are trying to get to.

@J. A. Whye - you mentioned “I have enemies traversing a grid-based play field but I don’t use Jumper or anything else because the movement is supposed to be random” how did you accomplish that? Because that is what I want to do - again, exactly like the type of random enemy movement in the video.

If I did use the jumper.grid module, how would I achieve the following:

  1. Make a custom grid with a size that covers the entire display - 1s corresponding to obstacles I’ve place via LH and 0s representing the area accessible to the player and enemies.

  2. The ability to translate x/y coordinates into a particular grid square and then using math.random (I assume ) code enemy tanks to roam around strictly confined to the squares with a value of 0 - so as to avoid the obstacles - and also have an option for restricting tank/s to a certain group of squares.

The Jumper files do include some explanations, but they are a little vague for a novice programmer like myself … :\

-Saer [import]uid: 148623 topic_id: 37290 reply_id: 145724[/import]