• Advertisement
Sign in to follow this  

Binary heap - resorting

This topic is 4584 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! I'm working on a little A* pathfinding algoritme, and it works fine, but i want to make it faster so i've implemented a binary heap. The heap works fire exept for one thing: Resorting. I've followed this tutorial: http://www.policyalmanac.org/games/binaryHeaps.htm Now it says this: As is described in the main article, occasionally you will find that the F score of an existing open list item can change. When that happens, you don’t need to take the item out of the list and start all over. Simply start in its current location, and compare it to its parent using its new (lower) F score. If its F score is low enough to warrant a swap with that parent, then you need to do so (or you will have an invalid heap, and everything will break down). In general, you use the same code described in the “Adding an Item to the Heap” section of this article, with the following additional consideration: ... This can't be right... can it?! If I would change the first ellement in the heap, it just stays there, 'cause it doesn't have any parent nodes... But when i update the heap like that, and then I want the lowest item, I will get the item that was lowest recently, but is now maybe way bigger then the smallest in the list... Any thoughts please? (PLEASE :p I really need some help..., 'cause this is just confusing). Thx in advance... Dauntless (I know this nick is taken by someone else, but still, i'm used to using 'Dauntless' as my nickname ;) Crappy 'DauntlessCrowd' :@ ) //EDIT I was thinking... Maybe this just never happens in A*... Maybe the highest F will NEVER be replaced, because its already the highest, and if another path to that node is shorter, that other tile would be in place 1, and the current tile would be 2 or 3 or whatever... Can anyone confirm that? Any A* wizzes here ?? [Edited by - DauntlessCrowd on July 29, 2005 7:28:57 PM]

Share this post


Link to post
Share on other sites
Advertisement
I don't know anything about A* but for a normal heap you'd have to check against both the parent and your children to make sure that the heap property is preserved. If not you'd either have to move the item up or down, possibly even multiple steps, in the tree to compensate. And that's probably not enough either..

Personally I'd implement the heap check and reinsert the item completely if it fails.

Share this post


Link to post
Share on other sites
Quote:
Original post by doynax
I don't know anything about A* but for a normal heap you'd have to check against both the parent and your children to make sure that the heap property is preserved. If not you'd either have to move the item up or down, possibly even multiple steps, in the tree to compensate. And that's probably not enough either..

I have a feeling that I'd be a lot easier just to remove and reinsert the item instead..


Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...

Share this post


Link to post
Share on other sites
Quote:
Original post by DauntlessCrowd
Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...
You're right of course, I just wasn't thinking. You'd have to rebuild the entire thing.

I suppose that it could work if the condition is rare enough, otherwise you'll have to choose a different datastructure.

Share this post


Link to post
Share on other sites
Quote:
Original post by doynax
Quote:
Original post by DauntlessCrowd
Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...
You're right, I just wasn't thinking. You'd have to rebuild the entire thing.

Jup, and that would just be stupid... But thx for the input, all thoughts are welcome :)

Share this post


Link to post
Share on other sites
Quote:
Original post by DauntlessCrowd
Quote:
Original post by doynax
Quote:
Original post by DauntlessCrowd
Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...
You're right, I just wasn't thinking. You'd have to rebuild the entire thing.

Jup, and that would just be stupid... But thx for the input, all thoughts are welcome :)
Another option would be to keep the node around but flag it as removed and only rebuild the heap when the amount of dead meat exceeds some magical limit, i.e. the garbage collection approach.

In general it should be possible to replace the heap with a balanced binary tree, unless you only need to keep track of the top matches or something. Keep in mind that the space overhead and constant factors will be a lot higher though.

Share this post


Link to post
Share on other sites
That would still be more time consuming... And what about adding a new node when its parent is deleted?

I was thinking... Maybe this just never happens in A*... Maybe the highest F will NEVER be replaced, because its already the highest, and if another path to that node is shorter, that other tile would be in place 1, and the current tile would be 2 or 3 or whatever...

Can anyone confirm that? Any A* wizzes here ??

Share this post


Link to post
Share on other sites
The point in A* is using the tile with the lowest F. So i've put all the F's in a binary heap so that i can easily find the lowest F. (And it also works, no problems there! :) ). Its just that it DOES happen that an F changes, so I would have to update my heap...

But I think i'm right with the fact that its just impossible... But if someone could please confirm that? :)

//edit
Uhm, did you delete your post or something?

//Another edit:
The thing in A* is: It would only be changed to a lower F. Changes of an F to a higher F dont occur. So I think it would also be stupid to check the children of the current node... (That's atleast with my small knowledge of the binary heap).

Share this post


Link to post
Share on other sites
Quote:
Original post by DauntlessCrowd
Uhm, did you delete your post or something?
I reread your original post and realized that you were just taking the top node as an example.

Quote:
Original post by DauntlessCrowd
The thing in A* is: It would only be changed to a lower F. Changes of an F to a higher F dont occur. So I think it would also be stupid to check the children of the current node... (That's atleast with my small knowledge of the binary heap).
It doesn't matter. If the value of any node in the heap (not just the one at the top) can change then you still have to rebuild the entire thing.

Share this post


Link to post
Share on other sites
You should try it out on paper... The explenation from the tutorial actually works... You still end up with a valid heap after the change... Exept afcourse when you want to change the first node.

Share this post


Link to post
Share on other sites
Quote:
Original post by DauntlessCrowd
You should try it out on paper... The explenation from the tutorial actually works... You still end up with a valid heap after the change... Exept afcourse when you want to change the first node.
It might just work, it does remind me of the insertion algorithm anyway..
Why didn't they teach us that trick in school?

Share this post


Link to post
Share on other sites
Realize that in A*, you normally insert MANY MANY MANY more nodes than you extract from the open list.
A common optimization I've seen is to store an unordered open list along with a small sorted list of 10 or so elements from the open list. When you need the next node, get it from the sorted list. If you need the next node and the sorted list is empty, use an insertion sort to move items from the unordered list to the smaller sorted list (moving the worst nodes back to the ordered list when the sorted part has too many).

When you insert a node to the open list, check if the new node is better than one in the small sorted part. If so (or if the sorted list isn't full), insert the node into the short list at the appropriate spot. Otherwise, put the node in the unordered part of the open list.

This way you only sort a few nodes at a time and only occasionally have to sort the whole thing.

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
Realize that in A*, you normally insert MANY MANY MANY more nodes than you extract from the open list.
A common optimization I've seen is to store an unordered open list along with a small sorted list of 10 or so elements from the open list. When you need the next node, get it from the sorted list. If you need the next node and the sorted list is empty, use an insertion sort to move items from the unordered list to the smaller sorted list (moving the worst nodes back to the ordered list when the sorted part has too many).

When you insert a node to the open list, check if the new node is better than one in the small sorted part. If so (or if the sorted list isn't full), insert the node into the short list at the appropriate spot. Otherwise, put the node in the unordered part of the open list.

This way you only sort a few nodes at a time and only occasionally have to sort the whole thing.


Interesting :). Just 1 question: When my sorted list is empty, then i have to fill it again. So I loop through the whole unsorted upen array and when I vind that the node is lower to one of the nodes in the array, I add it, and then remove the last element or something?

Looks a bit weird that this would work faster, since you could might as well just sort the whole unsorted open array (you run through it anyhow) and now you just do the same, except deleting all the nodes you wouldnt need...

Share this post


Link to post
Share on other sites
Basically you delete the last one in the sorted part, yes. The reason it's better not to sort the whole thing is that sorting the whole thing is basically O(n^2) and sorting the large part into the small part is O(m*n) with m=10 or so and n=much more you can see it'd be faster. Well, not really, it'd be O(n ln(n)) but I'm not sure what it'd reduce to with the m (but it would reduce quite a bit still). Because you're only comparing to a few in the short list, it's much faster to sort things into it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
Basically you delete the last one in the sorted part, yes. The reason it's better not to sort the whole thing is that sorting the whole thing is basically O(n^2) and sorting the large part into the small part is O(m*n) with m=10 or so and n=much more you can see it'd be faster. Well, not really, it'd be O(n ln(n)) but I'm not sure what it'd reduce to with the m (but it would reduce quite a bit still). Because you're only comparing to a few in the short list, it's much faster to sort things into it.

Wauw... I dont understand squat :D . Euhm, where can I find those formula structures explained? I don't really get that kind of math in school... I also found those formulas on wolfram and wikipedia, but since I didnt knew how to read them... Some explenation please? Or a site, or something else...

Share this post


Link to post
Share on other sites
If you are using C++, why don't you just use std::priority_queue? Here is how you might initialize and use it:


node temp;
std::priority_queue< node, std::vector< node >, std::greater< node > > node_queue;
temp = node_queue.top();
node_queue.pop();
node_queue.push(temp);


You can use any of the comparison operators, but std::greater and std::less are the only ones that would probably make sense.

For searches like A*, I create a node called informed_node that looks a bit like this:


struct informed_node
{
node* ptr_node;
int cost;
int current_cost;
int projected_cost;
void clone(node& n)
{
ptr_node = &n;
cost = 0;
current_cost = 0;
project_cost = 0;
}
const informed_node& operator=(cosnt node& n) { clone(n); return *this; }
bool operator>(const informed_node& n) { return cost > n.cost;
informed_node(const node& n) { clone(n); }
};


Then I define my priority queue like this:


std::priority_queue< informed_node, std::vector< informed_node >, std::greater< informed_node > >


When you push regular "node" objects into the priority queue, it creates an informed_node and calls the copy constructor. Why do this? Well, so you can skip having a closed list of nodes. You will have to keep some internal information in the node pointed to by ptr_node. Basically, just the current cost and whether or not it has been visited. You will also need to keep a list of alterned nodes, so you can change the current cost and the visited status back to their defaults. Also, whenever you come to a previously searched node, you can actually change the current cost of EVERY SINGLE NODE pointed to by ptr_node in the informed_nodes.

Doing this removes the need for a closed_list (because you can use the node pointed to by ptr_node to get the current cost and visited status), it also changes having to set all nodes in the search space to default values in the beginning to having to set only searched nodes to default values at the end. This will speed up your searches quite a bit.

Here, I'll just show you mine:


template <class Object, class Cost>
int search<Object, Cost>::a_star(node<Object, Cost>& start_node, node<Object, Cost>& goal_node, CostFunc cost_func)
{
int result;
m_nodes_searched = 0;
result = a_star_search(&start_node, &goal_node, cost_func);
if(result)
{
this->store_goal(&start_node, m_goal);
}
this->revert_altered_nodes();
return result;
}

template <class Object, class Cost>
int search<Object, Cost>::a_star_search(node<Object, Cost>* start_node, node<Object, Cost>* goal_node, CostFunc cost_func)
{
std::priority_queue< informed_node<Object, Cost>, std::vector< informed_node<Object, Cost> >, std::greater< informed_node<Object, Cost> > > node_queue;
std::list< node<Object, Cost>* >::const_iterator itr;
informed_node<Object, Cost> child;
informed_node<Object, Cost> node;
Cost current_cost;

start_node->m_visited = true;
start_node->m_cost = Cost();
m_altered_nodes.push(start_node);
node_queue.push(*start_node);

while(!node_queue.empty())
{
node = node_queue.top();
node_queue.pop();
if(node.m_node->m_object == goal_node->m_object)
{
m_goal = node.m_node;
return 1;
}
itr = node.m_node->get_connections().begin();
m_nodes_searched++;
while(itr != node.m_node->get_connections().end())
{
child.m_node = (*itr);
if(child.m_node->m_parent != node.m_node)
{
if(!child.m_node->m_visited)
{
child.m_current_cost = node.m_current_cost + cost_func(*node.m_node, *child.m_node);
child.m_projected_cost = cost_func(*child.m_node, *goal_node);
child.m_cost = child.m_current_cost + child.m_projected_cost;
child.m_node->m_parent = node.m_node;
child.m_node->m_visited = true;
child.m_node->m_cost = child.m_current_cost;
node_queue.push(child);
m_altered_nodes.push(child.m_node);
}
else
{
current_cost = node.m_current_cost + cost_func(*node.m_node, *child.m_node);
if(current_cost < child.m_node->m_cost)
{
child.m_current_cost = current_cost;
child.m_projected_cost = cost_func(*child.m_node, *goal_node);
child.m_cost = child.m_current_cost + child.m_projected_cost;
child.m_node->m_parent = node.m_node;
child.m_node->m_cost = current_cost;
node_queue.push(child);
}
}
}
itr++;
}
}

return 0;
}

Share this post


Link to post
Share on other sites
Quote:
Code...

Actually i'm using a super crapy language called Actionscript (comes with flash by MacroMedia). So... I AM planning on learning Java though...

Share this post


Link to post
Share on other sites
Well, never-the-less, you shouldn't have to rebuild (build heap) any kind of binary heap in an A* search. I would suggest looking into functions called percolate up and percolate down, and try to understand how those work. They are all you need to insert and delete things from a priority queue which is what you need for A*.

Share this post


Link to post
Share on other sites
You will need to reconsider any nodes that you come to more than once too. There are quite a few times when you will come to a previously searched node with a longer path than the previous time. If you update the current path without checking if the currently searched path is shorter than the previous one, then you will end up with a messed up path. Also, you might come to a previously search node with a shorter path too. If this occurs, then you will need to change the path to the shorter one.

What is your search space like, anyway? Is it just a grid? Is everything uniform cost (ie moving from tile to tile is just a cost of one)? If so, then you probably wouldn't get cases where coming across a previously search node would result in a lower cost. You could probably ignore that case completely. If not, then you will have to do what I described above.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zefrieg
You will need to reconsider any nodes that you come to more than once too. There are quite a few times when you will come to a previously searched node with a longer path than the previous time. If you update the current path without checking if the currently searched path is shorter than the previous one, then you will end up with a messed up path. Also, you might come to a previously search node with a shorter path too. If this occurs, then you will need to change the path to the shorter one.

What is your search space like, anyway? Is it just a grid? Is everything uniform cost (ie moving from tile to tile is just a cost of one)? If so, then you probably wouldn't get cases where coming across a previously search node would result in a lower cost. You could probably ignore that case completely. If not, then you will have to do what I described above.


Both variable cost & uniform costs are possible... But actually, my A* on its own is finished now, it works perfect and does the thing you descripe (if(newPath.f < oldPath.f){ changeParent; etc;};

All I need now is optimalisation tips, 'cause Flash really isnt fast, and I do WANT to make it FAST. Any general topics on that issue?

Share this post


Link to post
Share on other sites
Well, go ahead and throw your code up here. It might be easier to point out optimizations if we know what you have so far.

Share this post


Link to post
Share on other sites
Well, I hope you guys understand this language (ActionScript)... It's OOP, so that's a start and it has a basic .dot syntax. I have 3 classes: Astar, Tile and BinaryHeap.
Here goes:

Astar class

import be.dauntless.Astar.Tile;
import be.dauntless.Astar.BinaryHeap;

class be.dauntless.Astar.Astar
{

private var startPoint:Array;

private var endPoint:Array;

private var map:Array;

public static var standardCost:Number = 1;

private var mapH:Number;

private var mapW:Number;

private var clipping:Boolean = false;

private var heap:BinaryHeap;

/*
* Function: Astar (constructor)
* Constructor, sets 'clipping'
*
* Parameters:
*
* clipping - Boolean indicating whether or not clipping is aloud.
*
* Returns:
*
* Nothing
*/

public function Astar(c:Boolean)
{
clipping = c;
}

/*
* Function: setMap
* Set the map for the engine
*
* Parameters:
*
* _map - A 2d array of references to tiles, presenting the current map
*
* Returns:
*
* Nothing
*
* See Also:
*
* &lt;setStartPoint&gt;
*
* &lt;setEndPoint&gt;
*/

public function setMap(_map:Array):Void
{
this.map = new Array();
this.map = _map;
this.mapW = this.map[0].length;
this.mapH = this.map.length;
}

/*
* Function: newMap
* Build a new Map
*
* Parameters:
*
* x - width of the map
* y - height of the map
*
* Returns:
*
* Nothing
*
* See Also:
*
* &lt;setMap&gt;
*/

public function newMap(w:Number, h:Number):Void
{
w = Math.floor(w);
h = Math.floor(h);
this.map = new Array();
for (var y = 0; y&lt;h; y++)
{
map[y] = new Array();
for (var x = 0; x&lt;w; x++)
{
var tile:Tile = new Tile(x, y, Astar.standardCost);
map[y][x] = tile;
}
}
this.mapW = this.map[0].length;
this.mapH = this.map.length;
}

/*
* Function: setStartPoint
* Set the stating point (player position) for the engine
*
* Parameters:
*
* x - the x position of the player
* y - the y position of the player
*
* Returns:
*
* Nothing
*
* See Also:
*
* &lt;setEndPoint&gt;
*
* &lt;setMap&gt;
*/

public function setStartPoint(x:Number, y:Number):Void
{
this.startPoint = new Array();
this.startPoint[0] = x;
this.startPoint[1] = y;
}

/*
* Function: setEndPoint
* Set the map for the engine
*
* Parameters:
*
* x - the x position of the player
* y - the y position of the players
*
* Returns:
*
* Nothing
*
* See Also:
*
* &lt;setStartPoint&gt;
*
* &lt;setMap&gt;
*/

public function setEndPoint(x:Number, y:Number):Void
{
this.endPoint = new Array();
this.endPoint[0] = x;
this.endPoint[1] = y;
}

/*
* Function: findPath
* find a path from the startPoint to the endPoint in the given map
*
* Parameters:
*
* None
*
* Returns:
*
* array/Boolean - array containing references of tiles presenting the path from startpoint to endpoint OR false if no path was found.
*
*
*
* See Also:
*
* &lt;setStartPoint&gt;
*
* &lt;setEndPoint&gt;
*
* &lt;setMap&gt;
*/

public function findPath():Object
{
//if you reuse the same tiles, the tiles will be closed. So we need to open all the tiles:
openMap();

if(!ready()) return false;

//the binary heap
heap = new BinaryHeap();

//there is no path found yet
var pathFound:Boolean = false;

//start off with the first tile (startPoint).
//set it to open, calculate its G (0, 'cause it IS the startpoint), and H.
//and add that tile to the open array
var beginTile:Tile = map[startPoint[1]][startPoint[0]];

//hij moet open gezet worden want dit is nodig om na tekijken of hij al in open zit (regel 253 +- )
beginTile.setOpen();
beginTile.setG(0);
beginTile.setH(startPoint[0], startPoint[1], endPoint[0], endPoint[1]);
beginTile.setParent(beginTile);
heap.addToHeap(beginTile);

//as long as there is a tile that can be visited and no path is found...
//(if open is empty, there is no solution)
while(heap.getLength() &gt; 0 && !pathFound)
{
// the current-array always represents the current tile
var current:Tile = getLowestFTile();

//check if the path is found (current tile = end tile)
if(current.x == endPoint[0] && current.y == endPoint[1])
{
trace("Path was found");
pathFound = true;
break;
}

// remove the current object from the open-array
current.setClosed();

//find all the surrounding nodes
var neighbours:Array = findSurroundingTiles(current);
for(var i in neighbours)
{

//if this neighbour is not in the open-array
if(!neighbours.getOpen())
{
//add this neighbour to the open-array
//and calculate all the needed settings.
neighbours.setOpen();
neighbours.setParent(current);
neighbours.setH(neighbours.x, neighbours.y, endPoint[0], endPoint[1]);
neighbours.setG(current.getG());
heap.addToHeap(neighbours);

} else {
//calculate new F. If the new F is smaller, that means the way to this node trough
//the currentnode is shorter. So update that node to make current node its parent
//and calculate new G.
var tempF:Number = neighbours.getH() + current.getG() + neighbours.getCost();
if(tempF &lt; neighbours.getF())
{
var id = neighbours.id;
neighbours.setParent(current);
neighbours.setG(current.getG());
heap.updateList(heap.getPosition(id));
}
}
}
}

//if the open array is empty, no path was found
if(heap.getLength() == 0 && !pathFound){
trace("There is no path!");
return false;

}

//the path is calculated, so now we have to start at the end and work our way back:
var path:Array = new Array();
var px:Number = endPoint[0]; //pathX;
var py:Number = endPoint[1]; //pathY;
path.push(map[py][px]);
var parent:Tile = map[py][px].getParent();
px = parent.x; //pathX;
py = parent.y;

//as long as one of the two cordinates still isn't the same as the start point, continue
while (px != startPoint[0] || py != startPoint[1])
{
path.push(map[py][px]);
parent = map[py][px].getParent();
//map[py][px] returns the tile; getParent() returns its parent and x the x property of the tiles parent
px = parent.x;
py = parent.y

}


//and put the startPoint in there too
path.push(map[startPoint[1]][startPoint[0]]);
//we started at the endpoint, so now we have to reverse the array
path.reverse();

//and now we're all done so return the path!!!
return path;
}

/*
* Function: getLowestFTile
* find the tile in the open-array with the lowest F (best node to look at next).
*
* Parameters:
*
* None
*
* Returns:
*
* Tile - Reference to the tile with the lowest F
*
*/

private function getLowestFTile():Tile
{
return heap.getLowest();
}

/*
* Function: findSurroundingTiles
* find the surrounding tiles of the given tile. If clipping is set to true,
* 8 tiles will be scanned. If not: 4 tiles.
*
*
* Parameters:
*
* x - the x value of the tile
*
* Returns:
*
* array - array containing references to all the valid neighbour tiles
*/

private function findSurroundingTiles(current:Tile):Array
{
var st:Array = new Array(); //st = surroundingTiles
var x:Number = current.x;
var y:Number = current.y;

//check left, right, down and up. Check: walkable & not closed
if(map[y][x-1].walkable && !map[y][x-1].isClosed() )
{
st.push(map[y][x-1]);
map[y][x-1].costDown();
}
if(map[y][x+1].walkable && !map[y][x+1].isClosed() )
{
st.push(map[y][x+1]);
map[y][x+1].costDown();
}
if(map[y+1][x].walkable && !map[y+1][x].isClosed() )
{
st.push(map[y+1][x]);
map[y+1][x].costDown();
}
if(map[y-1][x].walkable && !map[y-1][x].isClosed() )
{
st.push(map[y-1][x]);
map[y-1][x].costDown();
}

if(clipping){
//check left-up, left-down, right-up and right-down. Check: walkable & not closed
if(map[y-1][x-1].walkable && !map[y-1][x-1].isClosed() )
{
st.push(map[y-1][x-1]);
map[y-1][x-1].costUp();
}
if(map[y-1][x+1].walkable && !map[y-1][x+1].isClosed() )
{
st.push(map[y-1][x+1]);
map[y-1][x+1].costUp();
}
if(map[y+1][x+1].walkable && !map[y+1][x+1].isClosed() )
{
st.push(map[y+1][x+1]);
map[y+1][x+1].costUp();
}
if(map[y+1][x-1].walkable && !map[y+1][x-1].isClosed() )
{
st.push(map[y+1][x-1]);
map[y+1][x-1].costUp();

}
}
return st;
}

/*
* Function: ready
* Check whether or not all the settings are correct
*
* Parameters:
*
* None
*
* Returns:
*
* Boolean - True: Game is ready, false: There was an error
*
*/

private function ready():Boolean
{
if(map == undefined){
trace("No map specified");
return false;
}
if(startPoint[0] != Math.floor(startPoint[0]) || startPoint[1] != Math.floor(startPoint[1]))
{
trace("Startpoint isn't valid");
return false;
}

if(endPoint[0] != Math.floor(endPoint[0]) || endPoint[1] != Math.floor(endPoint[1]))
{
trace("Endpoint isn't valid");
return false;
}

if(startPoint[0] &lt; 0 || startPoint[0] &gt;= mapW)
{
trace("Startpoint isn't valid");
return false;
} else if(startPoint[1] &lt; 0 || startPoint[1] &gt;= mapH){
trace("Startpoint isn't valid");
return false;
}

if(endPoint[0] &lt; 0 || endPoint[0] &gt;= mapW)
{
trace("EndPoint isn't valid");
return false;
} else if(endPoint[1] &lt; 0 || endPoint[1] &gt;= mapH){
trace("EndPoint isn't valid");
return false;
}

if(!map[endPoint[1]][endPoint[0]].walkable){
trace("Endpoint isn't walkable.");
return false;
}
if(!map[startPoint[1]][startPoint[0]].walkable){
trace("Startpoint isn't walkable.");
return false;
}
return true;
}

/*
* Function: setWalkable
* Toggle the tile to be walkable or not
*
* Parameters:
*
* x - x position of the tile
* y - y position of the tile
* walkable - boolean representing the ability to walk on the tile or not
*
* Returns:
*
* Nothing
*
* See also:
*
* &lt;toggleWalkable&gt;
*/

public function setWalkable(x:Number, y:Number, b:Boolean):Void
{
map[y][x].setWalkable(b);
}

/*
* Function: toggleWalkable
* Toggle the tile to be walkable or not
*
* Parameters:
*
* x - x position of the tile
* y - y position of the tile
*
* Returns:
*
* Nothing
*
* See also:
*
* &lt;setWalkable&gt;
*/

public function toggleWalkable(x:Number, y:Number):Void
{
map[y][x].toggleWalkable();
}

/*
* Function: setClipping
* Toggle clipping. Clipping is the ability to move diagonally.
*
* Parameters:
*
* clipping - Boolean representing the ability to use clipping
*
* Returns:
*
* Nothing
*/

public function setClipping(c):Void
{
clipping = c;
}

/*
* Function: openMap
* Opens the map (resets all the tiles)
*
* Parameters:
*
* None
*
* Returns:
*
* Nothing
*/

private function openMap(){
for(var y = 0; y&lt;mapH; y++){
for(var x = 0; x&lt;mapW; x++){
map[y][x].reset();
}
}
}
}


Tile class

import be.dauntless.Astar.*;

class be.dauntless.Astar.Tile
{

private var inOpen:Boolean = false;
private var closed:Boolean = false;

private var parent:Tile;

private static var ids:Number = 0;

private var gUp:Boolean = false;


private var h:Number;
private var g:Number;

private var cost:Number = Astar.standardCost;

public var x:Number;
public var y:Number;
public var id:Number;
public var walkable:Boolean = true;

/*
* Function: Tile
* Constructor. Set the x, y and cost of the tile;
*
* Parameters:
*
* x - x position of the tile;
* y - y position of the tile;
* cost - cost of the tile;
*
* Returns:
*
* Nothing
*/

public function Tile(xp:Number, yp:Number, cost:Number){
x = xp;
y = yp;
id = ids++;
this.cost = cost;
}

/*
* Function: setWalkable
* Set the ability to walk on this the tile
*
* Parameters:
*
* walkable - Boolean value whether or not the tile is walkable
*
* Returns:
*
* Nothing
*/

public function setWalkable(b:Boolean):Void
{
walkable = b;
}


/*
* Function: setOpen
* Set this tile to be in the open-array. This is used by the findPath method of the Astar class.
*
* Parameters:
*
* None
*
* Returns:
*
* Nothing
*
* See also:
*
* &lt;setClosed&gt;
*
* &lt;setWalkable&gt;
*/

public function setOpen():Void
{
inOpen = true;
closed = false;
}

/*
* Function: setClosed
* Set this tile to be in the closed-array. This is used by the findPath method of the Astar class.
*
* Parameters:
*
* None
*
* Returns:
*
* Nothing
*
* See also:
*
* &lt;setOpen&gt;
*
* &lt;setWalkable&gt;
*/


public function setClosed():Void
{
inOpen = false;
closed = true;
}

/*
* Function: isClosed
* returns whether or not the tile is in the closed list.
*
* Parameters:
*
* None
*
* Returns:
*
* closed - Boolean representing whether or not its closed
*/


public function isClosed():Boolean
{
return closed;
}

/*
* Function: getOpen
* returns whether or not the tile is in the open list.
*
* Parameters:
*
* None
*
* Returns:
*
* open - Boolean representing whether or not its open
*/


public function getOpen():Boolean
{
return inOpen;
}

/*
* Function: setParent
* sets the parent of the node
*
* Parameters:
*
* Tile - Parent of the node
*
* Returns:
*
* Nothing
*/


public function setParent(tile:Tile):Void
{
parent = tile;
}

/*
* Function: getParent
* Returns the parent of the node
*
* Parameters:
*
* None
*
* Returns:
*
* The parent of the node
*/


public function getParent():Tile
{
return parent;
}

/*
* Function: setH
* sets the H for the node. H is calculated with the manhatten method.
*
* Parameters:
*
* bx - number representing the x position of the tile
* by - number representing the y position of the tile
* ex - number representing the x position of the endPoint
* ey - number representing the y position of the endPoint
*
* Returns:
*
* Nothing
*/


public function setH(bx:Number, by:Number, ex:Number, ey:Number):Void
{
h = Math.abs(ex - bx) * cost + Math.abs(ey - by) * cost;
}

/*
* Function: setG
* Sets the G (cost) for the tile
*
* Parameters:
*
* g - the cost of the parent tile
*
* Returns:
*
* Nothing
*/


public function setG(_g:Number):Void
{
g = _g + getCost();
}

/*
* Function: getF
* Returns the F of the tile (F = G + H);
*
* Parameters:
*
* None
*
* Returns:
*
* F - The F of the tile
*/

public function getF():Number
{
return this.getG() + h;
}

/*
* Function: getH
* Returns the H of the tile
*
* Parameters:
*
* None
*
* Returns:
*
* H - The H of the tile
*/

public function getH():Number
{
return h;
}

/*
* Function: setCost
* Set the cost for the tile
*
* Parameters:
*
* cost - cost of the tile
*
* Returns:
*
* Nothing
*/


public function setCost(_cost:Number):Void
{
cost = _cost;
}

/*
* Function: getG
* get the G (cost) of the tile
*
* Parameters:
*
* None
*
* Returns:
*
* g - the total cost of the tile
*/



public function getG():Number
{
return g;
}

/*
* Function: getCost
* Returns the cost for the tile
*
* Parameters:
*
* None
*
* Returns:
*
* cost - the cost of the tile
*/


public function getCost():Number
{
var addCost:Number = (gUp)?1.414:1;
return cost * addCost;
}

/*
* Function: toggleWalkable
* Toggles the ability to walk on the tile
*
* Parameters:
*
* None
*
* Returns:
*
* Nothing
*/

public function toggleWalkable():Void
{
this.walkable = !this.walkable;
}


/*
* Function: reset
* This method resets the tile for further use
*
* Parameters:
*
* None
*
* Returns:
*
* Nothing
*/

public function reset():Void
{
this.inOpen = false;
this.closed = false;
this.closed = false;
this.parent = null;
this.h = null;
this.g = null;
this.gUp = false;
}

/*
* Function: costUp
* This method tells the node that its being accessed diagonally
*
* Parameters:
*
* None
*
* Returns:
*
* Nothing
*/

public function costUp():Void
{
this.gUp = true;
}

/*
* Function: costDown
* This method tells the node that its NOT being accessed diagonally
*
* Parameters:
*
* None
*
* Returns:
*
* Nothing
*/

public function costDown():Void
{
this.gUp = false;
}
}


Binary Heap

import be.dauntless.Astar.Tile;

class be.dauntless.Astar.BinaryHeap
{
private var heap:Array;

public function BinaryHeap()
{
heap = new Array(null);
}

public function addToHeap(newTile:Tile):Void
{
heap.push(newTile);
var cp:Number = heap.length-1; //cp = current position
var np:Number = Math.floor(cp/2);

//as long as the item isnt in the first position
while(cp != 1){
if(heap[cp].getF() &lt;= heap[Math.floor(cp/2)].getF()){
//if the current F is lower than or equal to its parent, switch them!
var t:Number = heap[Math.floor(cp/2)];
heap[Math.floor(cp/2)] = heap[cp];
heap[cp] = t;
cp = Math.floor(cp/2);
} else {
//destination reached!
break;
}
}
}

public function getLowest():Tile
{
var cp:Number = 1; //current position
var np:Number; //next position
var lowest:Tile = heap[1];
if(heap.length == 2){
heap.pop();
} else {
heap[1] = heap.pop();
}

while(true){
np = cp;
if(cp*2+1 &lt;= (heap.length -1) ){
if(heap[np].getF() &gt;= heap[np*2].getF() ) cp = 2*np;
if(heap[cp].getF() &gt;= heap[np*2+1].getF() ) cp = 2*np+1;
} else if(2*np &lt;= (heap.length -1)){
if(heap[np].getF() &gt;= heap[2*np].getF() ) cp = 2*np;
}

//check if np has changed, 'cause then we have to switch them
if(np != cp){
//switch heap[cp] & heap[np]
var t:Tile = heap[np];
heap[np] = heap[cp];
heap[cp] = t;
} else {
//position found, return!
return lowest;
}
}

}

public function getLength():Number
{
return (heap.length -1);
}

public function getPosition(id):Number
{
for(var i in heap){
if(heap.id == id){
return i;
}
}
}

public function updateList(cp_):Void
{
var cp:Number = cp_;
var np:Number = Math.floor(cp/2);

//as long as the item isnt in the first position
while(cp != 1){
if(heap[cp].getF() &lt;= heap[Math.floor(cp/2)].getF()){
//if the current F is lower than or equal to its parent, switch them!
var t:Number = heap[Math.floor(cp/2)];
heap[Math.floor(cp/2)] = heap[cp];
heap[cp] = t;
cp = Math.floor(cp/2);
} else {
//destination reached!
break;
}
}
}


}


[Edited by - DauntlessCrowd on August 3, 2005 12:29:54 PM]

Share this post


Link to post
Share on other sites
Well, your A* search seems fine to me. You might want to do something about the findSurroundingTiles function. You could keep a list in each tile of the connected tiles and just check whether they are walkable and not closed. That way, you don't have to create an array each time you search a tile. You would save quite a bit of time by doing that.

As for the binary heap, does the Action Script language have an integer type? That might work a bit better than the number type they seem to give you. That way you wouldn't have to call floor every time you divide by two.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zefrieg
Well, your A* search seems fine to me. You might want to do something about the findSurroundingTiles function. You could keep a list in each tile of the connected tiles and just check whether they are walkable and not closed. That way, you don't have to create an array each time you search a tile. You would save quite a bit of time by doing that.

And when do I have to store them there? At the beginning of the search? Loop through the whole map and set neighbours for evryone? (Probably not 'cause I would think that would go slower since otherwise you wouldnt even come to nodes where you do come to now...)

Quote:
As for the binary heap, does the Action Script language have an integer type? That might work a bit better than the number type they seem to give you. That way you wouldn't have to call floor every time you divide by two.
No, it doesn't have one... I dont know if Math.floor() is slow, but I can try some other methods ... see if they are faster :)

Thx anyway for looking through my code, which is in a language you don't even know! :) :)

Share this post


Link to post
Share on other sites
Why not use a Red-Black tree instead of a heap?
Insertion/removal complexity is O(log n). Search is O(log n) and it should be possible to get the first element in constant time.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement