# Turn-Based Tile Movement

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

## Recommended Posts

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!

##### Share on other sites
I realy dont 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 node might work or not!]

##### Share on other sites
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.

##### Share on other sites
I've been working on an Advance-Wars-esque project for a while (currently inactive, I'll continue working on it after my holiday). Perhaps this code can give you some inspiration. Feel free to dig around the project if you like. There's a pathfinding function in there as well as a function that checks for reachable tiles, taking terrain type and unit movement points into account. It's all fairly simple stuff, but don't hesitate to ask if there's something in there that you don't understand. I'm going on holiday for two weeks though, so I may not reply immediately. ;)

No need for recursion here, really - just store your bookkeeping data in a container and perform your logic in a loop. Either way, yeah, you may want to show your code. If a speed of 15 results in a 10-minute check, you're definitely doing something wrong.

##### Share on other sites
@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.

##### Share on other sites
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!

##### Share on other sites
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 :)

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633735
• Total Posts
3013597
×