Hey there! I've been sort of a lurker around here, but I hit a brick wall and I decided to ask the experts.

I'm working on a Fire Emblem/Final Fantasy Tactics/Advance Wars type game: a turn-based tile strategy game.

However, I'm having trouble making an efficient move function. I need to highlight the possible tiles that a unit can move to. As of now, here's how this works. If you guys need the actual code, just let me know.

I have a 2d array of Points called "highlightedTiles". This contains the current X and Y values of the highlighted tiles on the map.

When the player wants to move a unit, a function highlights the tiles that can be moved to. This function works like so.

I have 4 arrays of points. Each array is initalized using a recursive function which checks the adjacent tiles to see if they are either already highlighted in the current tree, occupied, or unoccupiable. If all of these requirements are false, then the tile is highlighted and it calls itself for each adjacent tile. If any of those requirements are true, the function simply returns. The recursive function takes the unit's speed and recurses speed - 1. If speed becomes 0, it will simply return.

So, imagine this scenario with a Unit whose speed is 3.

..X.......XX-.....XXXO|.....XXXXX.....XXX.......X.....

The O is the unit, dashes and '|'s are walls, and X's are movable locations highlighted correctly by the function. It works perfectly.

The problem is that once a unit's speed goes above 5, you start to notice the time it takes to loop through and find each tile. At about 10 speed in the middle of the map, it takes about 5 seconds. At 15 speed, it took about 10 minutes.

I know there has to be a more efficient way to do this. I'd appreciate any input you can offer me. Any links to other people's algorithms would be just as great.

If you guys want to see the code, just say the word.

Thanks!

I realy don`t understand how you use 4 arrays in this job.

1. build 2 dimenssional array (navMap) with size of (2*speed)^2
initialize movable cells to zero, and unmovable to magic number 256.
initialize players position to number of moves.

build coordinate list of CurrentlySpreadingFront[], and add position of player to it.

2. start flooding color :)

// pseudodo {coordinate = CurrentlySpreadingFront.popfront();// todo boundary checks!!!if (nawMap[coordinate.x][coordinate.y] -1 > nawMap[coordinate.x+1][coordinate.y]) {nawMap[coordinate.x+1][coordinate.y] = nawMap[coordinate.x][coordinate.y] -1;CurrentlySpreadingFront.pushback(coordinate(coordinate.x+1, coordinate.y));}if (nawMap[coordinate.x][coordinate.y] -1 > nawMap[coordinate.x-1][coordinate.y]) {nawMap[coordinate.x-1][coordinate.y] = nawMap[coordinate.x][coordinate.y] -1;CurrentlySpreadingFront.pushback(coordinate(coordinate.x-1, coordinate.y));}if (nawMap[coordinate.x][coordinate.y] -1 > nawMap[coordinate.x][coordinate.y+1]) {nawMap[coordinate.x][coordinate.y+1] = nawMap[coordinate.x][coordinate.y] -1;CurrentlySpreadingFront.pushback(coordinate(coordinate.x, coordinate.y+1));}if (nawMap[coordinate.x][coordinate.y] -1 > nawMap[coordinate.x][coordinate.y-1]) {nawMap[coordinate.x][coordinate.y-1] = nawMap[coordinate.x][coordinate.y] -1;CurrentlySpreadingFront.pushback(coordinate(coordinate.x, coordinate.y-1));}} while (size(CurrentlySpreadingFront[]) != 0);

3. read 2d navMap, values of x > 0 || x < 256 are acceptable movement tiles.

/Tyrian

Ps. </code>

This description doesn't sound right to me:

Quote:
Each array is initalized using a recursive function which checks the adjacent tiles to see if they are either already highlighted in the current tree, occupied, or unoccupiable. If all of these requirements are false, then the tile is highlighted and it calls itself for each adjacent tile.

Here's a version which sounds right:

Quote:
Each array is initalized using a recursive function which checks if the present tile is either already highlighted in the current tree, occupied, or unoccupiable. If all of these requirements are false, then the tile is highlighted and it calls itself for each adjacent tile.

@Tyrian: I used four arrays because I ran into a problem in which a unit had enough movement speed that the recursive function would cover the tile south of the unit so the south "tree" never got recursed.

@Wiggin: Yes, sorry about that. >_<

@Captain P: This looks great! Thank you very much! I'll adapt it to my game and see what happens.

Thank you very much, sir! I've adapted your code to my game.

I think I thought of an openList/closedList idea when I was looking into A* algorithms... I wonder what happened to that idea...

Well, it's working now, it can calculate a unit's movable locations with a speed of 30 in 1 frame! I owe you!

Here's my function if anybody else stumbles across this.

void Gamestate::HighlightMovableTiles(Unit* unit, int speed){	highlightedTiles.clear();	vector<DFUtilities::Point> openTiles;	// a DFUtilities::Point is a struct {int x, int y, int flags}	openTiles.push_back(unit->GetPosition());	// Pushes (push_back()) a tiles onto highlightedTiles	while (openTiles.size() > 0)	{		DFUtilities::Point currentPoint = openTiles.front();		HighlightTile(currentPoint.x, currentPoint.y, true);		// Adds to vector<DFUtilities::Point> highlightedTiles via push_back()		int currentDistance = currentPoint.flag;		openTiles.erase(openTiles.begin());		DFUtilities::Point adjacentPoints[4] = { 			{ currentPoint.x + 1, currentPoint.y, currentDistance + 1 }, 			{ currentPoint.x - 1, currentPoint.y, currentDistance + 1 }, 			{currentPoint.x, currentPoint.y + 1, currentDistance + 1 }, 			{ currentPoint.x, currentPoint.y - 1, currentDistance + 1 } };		for each (DFUtilities::Point p in adjacentPoints)		{			bool isHighlighted = false;			bool isOpen = false;			for (int i = 0; i < highlightedTiles.size(); i++)			{				if (highlightedTiles.x == p.x && 					highlightedTiles.y == p.y)				{					isHighlighted = true;					break;				}			}			for (int i = 0; i < openTiles.size(); i++)			{				if (openTiles.x == p.x && openTiles.y == p.y)				{					isOpen = true;					break;				}			}			if (p.x < 0 || p.x >= graphics.X_TILES || 				p.y < 0 || p.y >= graphics.Y_TILES || 				level.GetMap()->GetTile(p.x, p.y)-				>GetOccupied() || level.GetMap()-				>GetTile(p.x, p.y)->GetSolid() || p.flag 				> speed || isHighlighted || isOpen)			{				continue;			}			else			{				openTiles.push_back(p);			}		}	}}

Credits are given to you in the code with a link to your .py file!

Where did you calculate the tile distance (which appears to be inside flag)? If you already have that information, then you don't need any pathfinding algorithm or open/closed lists at all -- just iterate over a square region of tiles centered on the unit, where the side length of the square is twice the speed. Unless you omitted something :)