Tile based game data structure

Question

I've been working on a top down 2d game and the character moves freely around the map, like zelda link to the past.

How would you model the data structure for such a game in order to implement pathfinding, astar, etc.

As far I understood one could go with this approach:

Tile {
 sprite,
 walkable,
 position,
}

Board {
  width
  height
  tiles: Tile[]
}

In a board of 5x5 there will be a sprite rendered for each tile. But here comes the problem:

The player is at position (+1,+1). Now it moves to the right side (+2,+1). This will mean that the player is moved immediately from one tile to another. So, we could make the player move pixel by pixel. How would you translate this back to the grid position?

If player moves pixel by pixel (using floating point instead of integers) and is at position (1.5,1),doest it means we need a separated data to store player position and later on round its current position (1.5, 1) to find its current cell in the grid?

I'm kind lost in this subject, i would love if you could share some thoughts on it, articles, videos, books, etc.

Thanks!

Answer 1

I'd probably use those three variables:

Vector2i previousTile
Vector2i nextTile
float transition

Previous and next tile are pretty self explainatory. If player wants to move, nextTile is set to his target coordinates (eg. [2, 1]). Player is in "moving" state if previous and nextTile are different. The "transition" field is used to tell where the player is now, from 0 (not started moving) to 1 (finished moving). Anything lower than 0.5 would mean that, as far as game logic carse, the player is still at previousTile. Anything greater or equal -> player is at nextTile. You might want to introduce additional field, or helper function that will tell you where the player is at the moment:

currentTile = (transition<0.5) ? previousTile : nextTile;

With that approach, you can play with how fast player moves between tiles (by changing how much you add to "transition" variable per frame).

function Update(float timeStep)
    if(previousTile==nextTile)
        return

    transition += timeStep * 2
    // *1 => distance between adjecent tiles in 1 second
    // *2 => ^ twice as fast, in 0.5s

    // Make sure we do not exceed 1, otherwise player will overshoot his target
    if(transition>1)
        transition=1

    currentTile = (transition<0.5) ? previousTile : nextTile;

As for the drawing, you'll have to interpolate player's sprite position:

function Draw()
    Render.DrawAt(previousTile*(1-transition) + nextTile*transition)

Probably you'll want to change previousTile and nextTile in above example to locations of those tiles on the screen.