Jump to content
  • Advertisement
Sign in to follow this  
comstation11

Turn-Based Tile Movement

This topic is 2995 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

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 this post


Link to post
Share on other sites
Advertisement
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 :)

// pseudo

do {
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 :)

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!