Any good references for isometric A*?

[doomtoo]

I've found a couple good sites with the A* algorithm, and one good one in flash, but anyone else have some helpful links on implementing the A* algorithm?

[TOdorus]

A* isn't isometric, or topdown or any kind of perspective. It's algorythm that needs a graph (nodes with connections to other nodes), which is void of perspective.

That bieng said, this is the link (http://www.policyalmanac.org/games/aStarTutorial.htm) I always use as a reference when I need to do something A*.

[doomtoo]

Yeh, I was just unsure about giving the different directions different weights/costs, because going straight in any direction would actually be "diaganol" in the game world and should cost more/move slower.. Thanks for the link!

[doomtoo]

This might apply here also, is it better to represent your tiled map(for pathfinding and further use) as a 1 dimensional or 2d array? I normally do 1d but could do either:

[1, 0, 0, 1,
1, 0, 0, 1,
1, 0, 0, 1]
or
[[1, 0, 0, 1]
[1, 0, 0, 1]
[1, 0, 0, 1]]

[TOdorus]

2D means two lookups every time a tile is checked. 1D means 1 lookup, so if you can work that way you can half the time you need for every tile lookup.

[BoppreH]

2D means two lookups every time a tile is checked. 1D means 1 lookup, so if you can work that way you can half the time you need for every tile lookup.
But you will either need a hell of a wrapper class or you will blow your mind.

Maybe storing the matrix as BitmapData is even faster?

[TOdorus]

But you will either need a hell of a wrapper class or you will blow your mind.

That's a bit of an overstatement. One variable containing your rowlength and function converting 2D coordinates and getting the appropiate value out of an array is enough.



private var rowLength:int
function getTile(X:int, Y:int):int{
var ArrayPosition:int = (Y*rowLength) + X
return(tileArray[ArrayPosition])
}


Just another set function and you're... set (I know bad pun). doomtoo already showed that it writes in quite the same manner if you do not use a tile editor, so there really is no reason not to use a 1D array. Except maybe for:


Maybe storing the matrix as BitmapData is even faster?

Never tried that actually, but I've heard that getPixel() is kind of slow



import flash.display.BitmapData;
import flash.utils.getTimer
//
var TESTBMP:BitmapData = new testBMP(0,0)
var TESTARRAY:Array = []
var i:int
var total:int = 50000000
var timer:int
var testValue:int
//
for(i = 0; i < total; i++){
TESTARRAY.push(i)
}
//
//
//
trace("==============")
trace(" 1D ARRAY ")
trace("==============")
timer = getTimer()
//
for(i = 0; i < total; i++){
testValue = TESTARRAY[i]
}
trace((getTimer()-timer)+" ms")
//
//
//
trace("==============")
trace(" BITMAPDATA ")
trace("==============")
timer = getTimer()
//
for(i = 0; i < total; i++){
testValue = TESTBMP.getPixel(0,0)
}
trace((getTimer()-timer)+" ms")




==============
1D ARRAY
==============
4228 ms
==============
BITMAPDATA
==============
7443 ms


That goes into the "too bad" box.

[doomtoo]

Cool, thanks! Yeah, I finally got everything working properly. I had been doing a bunch of things wrong, and finally figured how to do "pointers" in AS3, which helped a bit.

(Assign a value to a object without first creating a new version- I.E
var j:int=2;
var i:int=j;
j=26;
Output:
j=2, i=2
j=26, i =26 -whereas creating i as a new int and assigning it j's value, then changing j's value will not change i)

I used this tutorial:
http://lassieadventurestudio.wordpress.com/2008/12/09/a-star-pathfinding/

I still don't understand every part of it, but that link that was given gave me a much better understanding of f g and h.

I've been doing everything in a 1D array so far, and yeah, just fetch the proper tile using tiles[numX*y+x] -although had to figure the formula out using excel yet again...

One disadvantage is that you have to store extra data. I store each tile's worldX and Y value, along with it's actual number in the array for each tile.

Thanks for all the help!

[sada]

Yeah everybodys are right.Thang u.

[BoppreH]

That's a bit of an overstatement. One variable containing your rowlength and function converting 2D coordinates and getting the appropiate value out of an array is enough.



private var rowLength:int
function getTile(X:int, Y:int):int{
var ArrayPosition:int = (Y*rowLength) + X
return(tileArray[ArrayPosition])
}


Just another set function and you're... set (I know bad pun). doomtoo already showed that it writes in quite the same manner if you do not use a tile editor, so there really is no reason not to use a 1D array. Except maybe for:



Never tried that actually, but I've heard that getPixel() is kind of slow

That goes into the "too bad" box.
Too bad. But I'll try it regardless because of the excellent methods like "floodFill" and "threshold".

Ah, and the speed difference between 1D and 2D array must be enormous, because last time I checked BitmapData access time was better than 2D array's by a good factor.

[BoppreH]

TOdorus, I have news about using BitmapData as a matrix. This is a more real-world test, because we are not accessing the pixel 0,0 a few hundred million times, and only once.


const SIDE:uint = 1500
var i:int, j:int
var bitmap:BitmapData = new BitmapData(SIDE, SIDE)

function bitmapFunction() {
var allEqual:Boolean = true
var initialValue = bitmap.getPixel(0, 0)
for (var i:uint = 0; i < SIDE; i++) {
for (var j:uint = 0; j < SIDE; j++) {
if (!(bitmap.getPixel(i, j) == initialValue)) {
allEqual = false
break
}
}
}
return allEqual
}

var matrix:Array = new Array()
for (i = 0; i < SIDE; i++) {
matrix[i] = new Array()
for (j = 0; j < SIDE; j++) {
matrix[i][j] = 0
}
}

function matrixFunction() {
var allEqual:Boolean = true
var initialValue = matrix[0][0]
for (var i:uint = 0; i < SIDE; i++) {
for (var j:uint = 0; j < SIDE; j++) {
if (!(matrix[j][i] == initialValue)) {
allEqual = false
break
}
}
}
return allEqual
}

var oneD:Array = new Array()
for (i = 0; i < SIDE; i++) {
for (j = 0; j < SIDE; j++) {
oneD[i * SIDE + j] = 0
}
}

function oneDFunction() {
var allEqual:Boolean = true
var initialValue = oneD[0]
for (var i:uint = 0; i < SIDE; i++) {
for (var j:uint = 0; j < SIDE; j++) {
if (!(oneD[i * SIDE + j] == initialValue)) {
allEqual = false
break
}
}
}
return allEqual
}

import boppreh.Time

trace("1D array:", Time.timeFunction(oneDFunction, null, 5))
trace("BitmapData:", Time.timeFunction(bitmapFunction, null, 5))
trace("1D array:", Time.timeFunction(oneDFunction, null, 5))
trace("BitmapData:", Time.timeFunction(bitmapFunction, null, 5))
trace("1D array:", Time.timeFunction(oneDFunction, null, 5))
trace("BitmapData:", Time.timeFunction(bitmapFunction, null, 5))
trace("1D array:", Time.timeFunction(oneDFunction, null, 5))
trace("BitmapData:", Time.timeFunction(bitmapFunction, null, 5))

Time.timeFunction(bitmapFunction, null, 5)
returns the time required to run the "bitmapFunction", with "null" arguments, using the average value of "5" runs.

Results:

1D array: 175.6
BitmapData: 194.4
1D array: 252.2
BitmapData: 195.2
1D array: 258.6
BitmapData: 200.6
1D array: 253.6
BitmapData: 197


Strange enough, the array starts faster and becomes slower at the end.

Any idea of what happened?

[doomtoo]

Wierd.... Thats a decent time difference, I need to shave down as much processing time as possible!

Logically the Array is a simpler structure and should take less time....

[BoppreH]

Wierd.... Thats a decent time difference, I need to shave down as much processing time as possible!

Logically the Array is a simpler structure and should take less time....

But the BitmapData uses a different way to process things.

And things like adding/removing/moving large portions of the map will be way faster without doubt.

[TOdorus]

TOdorus, I have news about using BitmapData as a matrix. This is a more real-world test, because we are not accessing the pixel 0,0 a few hundred million times, and only once.

Strange enough, the array starts faster and becomes slower at the end.


I have to comment on your test, as you're not optimally using arrays. You should hardtype a variable and use that to skip the processing needed for Flash to figure out what's in an array.



var Value:int
for(i = 0; i < Length; i++){
Value = myArray[i] //The player now knows that myArray[i] is an integer
}


Since an array can contain all types of objects (in contrast to bitmapData's properties) this could shave off some time.

Btw isn't eval AS2? If you're serious about using bitmaps and speed then you should consider AS3.



But the BitmapData uses a different way to process things.

And things like adding/removing/moving large portions of the map will be way faster without doubt.

In a practical perspective I don't see much benefit in that. Large portions of the map are accesed in a editor and while the game is running it is mostly on a per-tile bases. I'm curious what your game is like that it would need that.

[BoppreH]

I have to comment on your test, as you're not optimally using arrays. You should hardtype a variable and use that to skip the processing needed for Flash to figure out what's in an array.



var Value:int
for(i = 0; i < Length; i++){
Value = myArray[i] //The player now knows that myArray[i] is an integer
}


Since an array can contain all types of objects (in contrast to bitmapData's properties) this could shave off some time.

Btw isn't eval AS2? If you're serious about using bitmaps and speed then you should consider AS3.




In a practical perspective I don't see much benefit in that. Large portions of the map are accesed in a editor and while the game is running it is mostly on a per-tile bases. I'm curious what your game is like that it would need that.
I think I missed something: where did I use "eval"? And I'm already using AS3.

I didn't use it for any big thing. Just things like tetris and snake games. I just wanted to make my engine as full-featured as possible.


What's even more strange is that changing computers dramatically affected the difference. And typing the array as you said yield the following result:

1D array: 141.6
BitmapData: 261.2
1D array: 142.8
BitmapData: 262.6
1D array: 143
BitmapData: 262.6
1D array: 143
BitmapData: 262.2


I guess it will stay in the Too Bad box for quite some time.

[TOdorus]

I think I missed something: where did I use "eval"? And I'm already using AS3.

Sorry total brainfart there.


I guess it will stay in the Too Bad box for quite some time.

Well, you could use bitmapData to save maps to an image file and let users exchange maps. You could always convert it into an array on load, so it really has some future.