# Tile based game data structure

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!

• Try to separate your notion of the logical game state from the pixels you draw on the screen. Logically, your player character is only ever in Tile 0 or Tile 1 — there's no such thing as Tile 0.5 as far as the core game rules need to care. Where your rendering system chooses to draw the sprite representing your character based on its walk animation state is a completely separate problem that has no necessary relationship to your board data structure. You could write a dozen different rendering systems that each render the same underlying board state in different perspectives and styles. – DMGregory Nov 6 '19 at 12:29
• @DMGregory is there any material out there to help break through the core and the view system? It feels that things starts to get complicated once you mixed both concepts. – Renan Valentin Ferreira Nov 6 '19 at 22:18

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.

• thanks a lot @crueltear! it is so hard to separe the core from the rendering logic – Renan Valentin Ferreira Nov 6 '19 at 22:15