Jump to content
• Advertisement

# Spatial Partitioning in a Hyper Light Drifter Kind of Game (Question)

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

I want to make a game similar to Hyper Light Drifter or Titan Souls in these aspects:

1. Tile Based

2. Open World

3. Enemy Encounters (Like in Hyper Light Drifter)

I'm not sure what kind of spatial partitioning I should be using, will a grid be good enough or should I go for something more complex like a Kd-tree, loose quadtree, etc.?

I'd also like to know how should I store the map. For instance, if there is a zone that is 500x500 tiles, should I separate the map in different smaller "zones"? Would that increase performance?

Thanks in advance for the help!

#### Share this post

##### Share on other sites
Advertisement

It probably depends on the size of the open world.  I've not played either of your examples, but they do seem to break up the world by having transitions.  In which case a grid of grids would probably be okay.  I'd go with the simplest method, abstract it out so nothing has to know what method you're using, and then swap to a more complex method when you need to.

#### Share this post

##### Share on other sites

Yup, size is the important factor here. Lets say you wanted to make exactly hyper light drifter. I'll just go all out and say:

A simple grid will be enough. By the amount of interactive NPCs per screen, a simple O(n^2) "check every NPC with every other NPC" ie. for collision detection will be entirely fast enough for this game (since from what I've seen there is like a max of ~10 moving NPCs active at once, mostly enemies, and until you get to multiple hundreds or maybe thousands of items, n^2-algorithms will generally be fast enough).

As long as you don't forsee having something like 10000 NPCs that all need full movement with collision detection at one time, using something like quadtrees will not gain you much - yes, you will increase performance, but at a factor that doesn't matter. You have 16.66 ms that you can fill. Why would you not chose the faster algorithm though? Well of the added complexity, which will take development time that could be spent on more important tasks.

(Thinking about it, for a small number of "entities" the simple each-vs-every style algorithms might actually even be faster than having to update and query a compliated data structure like quadtrees and the like, due to cache locality)

I'd also like to know how should I store the map. For instance, if there is a zone that is 500x500 tiles, should I separate the map in different smaller "zones"? Would that increase performance?

Why, of course this won't magically increase performance, it depends on what you do with those zones. For example, with rendering a uniform size tilemap, you can easily render any size of tilemap by looking just at as many tiles as the screen can fit, like with this pseudo-code:

const Vector2 startTile = cameraPos / TILE_SIZE;
const Vector2 numTilesToLookAt = screenSize / TILE_SIZE;
const Vector2 endTile = startTile + numTilesToLookAt;

for(int i = startTile.x; i < endTile.x; i++)
{
for(int j = startTile.y; j < endTile.y; j++)
{
vTilemap[i][j];
}
}


This will run equally fast for a 100*100 tilemap as with a 100000*10000000 tilemap, so you gain nothing by dividing the tilemap into zones. In fact, you might make matters worse as you will now have to handle drawing from multiple zones instead of being able to just access from the one zone vector.

I would probably only do this separation if you have to, like if your tilemap is so huge without transitions, that you cannot possibly fit it into memory at once - or if it is huge and you have to append/remove huge blocks at once at runtime. So not the common case in what I can see.

Edited by Juliean

#### Share this post

##### Share on other sites

"Open World" is not what you think it means in this case. Open World implies that there's an infinite number of paths that you can take to get from point A to B. Hyper Light Drifter appears to be using paths from the video's I looked up. And I don't know what the other is. It should also be noted that open world will not make your game instantly better. It can very much just be setting a completely unrealistic goal, or destroy what could have been a great game.

And usually with tiled, or sprited games... they do a few different things.

The first one and normally the most common one is that the entire level gets compiled into a single image with depth values written into it ahead of time. This reduces the need to constantly reupload the stupid map to the GPU each time you want to render a scene. Anything that is dynamic just becomes an additional object in the world.

For spatial partioniong for all of your tile by tile logic... you can just set meshs down and this will let your engine run some logic behind the scenes without the need of constantly checking tiles.

For partitioning the world... you can do a few things. but it needs to be done carefully.

The first one is terrain paging. But you need to set the distance out far enough for this to work. So it won't be noticed by the players. This can give you an open world... but for a sprite based game... I highly suggest not doing  that at all.

The second method is the Zelda transition. Which it simply loads in more of the map as you transfer from one area to the next with a scrolling screen.

The third is the fade in and fade out.

#### Share this post

##### Share on other sites
Thanks guys for your help, I will go with a world similar to Hyper Light Drifter, with paths and not too many enemies. I'll go with a grid of grids as it will be easier to create and handle smaller zones.

As for collission detection, I'll just check for objects inside a range of tiles (the tiles will have a pointer to each object that in that tile or something similar).

Thank you all for your tips and overall help, really love this community! :)

Ps: do I need to close this thread or something? Or do I just leave it as it is?

#### Share this post

##### Share on other sites

Thanks guys for your help, I will go with a world similar to Hyper Light Drifter, with paths and not too many enemies. I'll go with a grid of grids as it will be easier to create and handle smaller zones.

As for collission detection, I'll just check for objects inside a range of tiles (the tiles will have a pointer to each object that in that tile or something similar).

Thank you all for your tips and overall help, really love this community! :)

Ps: do I need to close this thread or something? Or do I just leave it as it is?

Just leave it up, you can revisit it if you'd like, and update us with the method you went with, and how well it did or didn't work out.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
19
5. 5
• Advertisement

• 14
• 26
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631771
• Total Posts
3002253
×

## 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!