Hi,

I'm a little lost at the moment (can't seem to wrap my head around it) so I thought I'd try here. I have created an ActionScript3 implementation of A* and I'm wondering if I could have a little bug in my implementation. I can't think of a situation where it might go wrong, but maybe you guys can.

So, here's a little fragment of my code:

//loop over all the neighbours of the current nodewhile(i-- > [[0]]){	//cN is the current neighbor that is being examined	cN = neighbours as DataTile;	//makes sure that cN.getCost() is multiplied by [[[1]]].[[[4]]] if this path is diagonalcN.setDiag(_map.isDiagonal(current.getPosition(), cN.getPosition()));					if(!cN.getOpen())	{		//add to open-array							openTile(cN, cN.getPosition(), current.getG(), this._end, current);	}	else	{		//already in open, check if F via current node is lower			newF = cN.calculateUpdateF(current.getG()); 		if(newF < cN.getF())		{			pos = this._heap.getPosition(cN);						cN.setParent(current);			cN.setG(current.getG());			this._heap.update_heap(pos);			}	}}

I think the code is pretty self explanatory, but if it's not, just let me know.

Now, the actual question: I think that 'cN.setDiag()' shouldn't be there. setDiag() makes sure that getCost() is multiplied by 1.4 if you access it diagonally. I think that the multiplier should only be used in calculateUpdateF (since you might want to access the tile diagonally) and right before/after calling setParent()

getCost() is used in calculateUpdateF() and is of course used in the getF() that's used by my binary heap to get the next best option.

If I'm asking for too much or my code isn't clear enough or anything else, just let me know.

Thanks!

Brain

19,059

September 05, 2010 05:21 AM

i dont know if this helps, but when i implemented this in C++ i had methods to calculate F, G and H which were defined when the open list object was instantiated and never changed afterwards. Instead of a setdiag, i had a Cost() function which returned 10 for non-diagonal squares and 14 for diagnonal squares, given the x and y position of the centre square and the x and y position of the square being checked (this can simply be represented as abs(x1-x2) == 1 && abs(y1-y2) == 1)

This is the part of my code that adds the eight neigbours, similar to your own code snippet:

                /* Add all eight adjacent squares to the OPEN list */                for (int x = Curr->x - 1; x < Curr->x + 2; ++x)                {                        for (int y = Curr->y - 1; y < Curr->y + 2; ++y)                        {                                if (x == Curr->x && y == Curr->y)                                        continue;                                /* Ignore unwalkable squares */                                if (!IsUnwalkable(unwalkable, Point(x, y), Start))                                {                                        /* Find out if this square is already on the OPEN list */                                        std::map<int, Location*>::iterator item = List.find(LHASH(x, y));                                        Location* newloc = NULL;                                        /* If it is, we need to find out which is better, our new version, or the old version                                         */                                        if (item != List.end())                                        {                                                /* Replace it, if our G-score is better than the old one */                                                if (item->second->Open())                                                {                                                        if (item->second->GetG() > Curr->GetG() + (Cost(Curr->x, Curr->y, x, y)))                                                        {                                                                delete item->second;                                                                newloc = new Location(x, y, Curr);                                                        }                                                        else                                                                /* Keep it if the old square is better scored */                                                                continue;                                                }                                                else                                                        /* Item exists, but is in the closed list, we don't mess with it */                                                        continue;                                        }                                        else                                        {                                                /* Item is in neither open or closed list, add it to the OPEN list */                                                newloc = new Location(x, y, Curr);                                        }                                        /* For the new item we added (if we added one) set te G score and the H score.                                         * As above, G score is the cost to get to this square from the starting position,                                         * and the H score is the cost to get to this square from the END location ignoring                                         * unwalkables and travelling only horizontally and vertically.                                         */                                        newloc->SetG(Curr->GetG() + (Cost(Curr->x, Curr->y, x, y)));                                        newloc->SetH(End);                                        List[LHASH(x, y)] = newloc;                                }                        }                }

Hope this helps!

Games/Projects Currently In Development:
Discord RPG Bot | D++ - The Lightweight C++ Discord API Library | TriviaBot Discord Trivia Bot

DauntlessCrowd

Author

122

September 05, 2010 06:06 AM

Thanks for your input!

For your implementation to work, you would have to create a new tile object if a better path to an already open tile is found, right? (It seems like that way in your code too). This would confirm my that the f() (and the cost()) of the new tile should only change when a better path has been found, which would suggest that my implementation is 'wrong'.

So I now know how it should be programmed, but I'm wondering if my current implementation can actually generate false results ...

Brain

19,059

September 06, 2010 02:53 AM

Hi DauntlessCrowd,

yes you should only change the tile's values if the F score is less than the score of the tile it is to replace and is not on the closed list.

I used the following tutorial to produce my algorithm which i found very useful: http://www.policyalmanac.org/games/aStarTutorial.htm

Games/Projects Currently In Development:
Discord RPG Bot | D++ - The Lightweight C++ Discord API Library | TriviaBot Discord Trivia Bot

A* possible bug in my implementation?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A* possible bug in my implementation?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines