Help on an Infinite Tile Engine

[callowaysutton]

So I want to make a tile engine that has the capacity to grow infinitely but I don't know how to put the concept into code.
I know how I would make a fix sized world which would just to have an array of a fixed size and then interact with that but it doesn't seem like the same concept would work on a game in which the world size is changing.
I was thinking of maybe just splitting it into chunks of arrays and then have each array put into another array but then I would still not know what to do like when something updates in one chunk that involves moving over to another chunk (imagine a roguelike monster moving around).
Lastly, I'm still pretty new to this language and don't know all the bells and whistles

Any help will be greatly appreciated and I'll post the source for others

[Tourist Trap]

Any help will be greatly appreciated and I'll post the source for others

Hello,

I tried this a while ago. Maybe it can help?
viewtopic.php?f=15&t=24355&p=215514#p215514

Your best luck otherwise would be to search the forum for topics on tiles from BasicCoder2. He made a great deal of very good stuff than you can trace back around here with a search on the forum.

[badidea]

Hi, a real infinite world will be difficult. There is not enough storage space in the universe for that :-)

Assuming rectangular/square grid (e.g. not hexagonal):

Chunks of of 2D-array is a good way. Because 2d-grids are nice for collision detection or for determining which enemies are close.

One could just use one dynamic 2d-array. Lets say, you start on tile 0,0 and create an array of size x:-10...+10 and y:-10...+10 (this minus is possible in freebasic) and when you move left one tile, you increase the world to x:-11...+10 and y:-10...+10 using "redim preserve". But this is inefficient:
a) For each "redim preserve" freebasic might need to allocate new memory, copy the existing data to this new memory block, free the old block.
b) If you move / walk diagonally, the array needs to grow quadruple, with memory allocated for area's you may never visit.

So chunks. With of an array of chucks, you have the same problems as above. So a list of chucks!
For each chunk, you keep track of which chuck is above, below, left an right of it.
This list of chunks, you could do again with a "redim preserve", but more efficient is a "linked list" (duckduckgo it).

Lets say you start on chunk 0. You move left first. At some point new tiles are needed. Create chunk 1, left of chunk 0.
Tell chunk 1 (via a variable or pointer) that chuck 0 is on its left. Tell chunk 0 that chunk 1 is on it right.
Now our character turns around and starts walking right. At some point new tiles are needed right of the first chunk 0.
Create chunk 2. Again set right of chunk 0 is 2. Set left of 2 is 0.

To figure out how an enemy, or your own character crosses the boundary of 2 chunks is a nice coding exercise :-)

Anyway, chunks are used by e.g. minecraft. Ever seen a minecraft map?
Search for e.g. "minecraft kurtjmac far lands or bust map". He has been walking for years in one direction only :-)

[Tourist Trap]

Hi, a real infinite world will be difficult. There is not enough storage space in the universe for that :-)

Not sure, it could grow from a procedural seed. I mean like a fractal for example. In any case, once sufficently grown (far before infinity), no player would be able to visit every places without the feeling of infinity, and shouldn't it be sufficent?

[badidea]

Hi, a real infinite world will be difficult. There is not enough storage space in the universe for that :-)

Not sure, it could grow from a procedural seed. I mean like a fractal for example. In any case, once sufficently grown (far before infinity), no player would be able to visit every places without the feeling of infinity, and shouldn't it be sufficent?

Ah yes, if you are not allowed you change the world (like in minecraft), an infinite world would require 0 storage, just code. (I think).

[callowaysutton]

Hi, a real infinite world will be difficult. There is not enough storage space in the universe for that :-)

Not sure, it could grow from a procedural seed. I mean like a fractal for example. In any case, once sufficently grown (far before infinity), no player would be able to visit every places without the feeling of infinity, and shouldn't it be sufficent?

Haha yeah although that's going more into the theoreticals, I'm talking about something that is 'potentially' infinite. I liked how Badidea's concept was going (that's a nice oxymoron for u) and I'll try researching to figure out more information.
I do have another question now though, how do you know what chunks you should generate around the player at any given coordinate? Is it really as simple loading and unloading chunks less than a certain amount of distance away from the player, or would that be inneficient?

[paul doe]

So I want to make a tile engine that has the capacity to grow infinitely but I don't know how to put the concept into code.
...

Welcome. What you need is called a spatial hash. This data structure is used, among other things, to quickly locate sets of nearby objects on a discrete grid (to quickly detect collisions between objects, for example), and can also be used for what you want (I think I posted an implementation on that, but can't find it, alas).

...
I know how I would make a fix sized world which would just to have an array of a fixed size and then interact with that but it doesn't seem like the same concept would work on a game in which the world size is changing.
...

It works pretty much the same way, but you'll have to implement this all by yourself (and that includes the spatial hash, since FreeBasic doesn't provide you with any datatypes you can use as a base except for arrays).

...
I was thinking of maybe just splitting it into chunks of arrays and then have each array put into another array but then I would still not know what to do like when something updates in one chunk that involves moving over to another chunk (imagine a roguelike monster moving around).
...

That scheme could be used to seamlessly stream chunks of the map from disk, or to persist changes to them (in case this is a requirement). Pretty much like Dungeon Siege did it.

...
Lastly, I'm still pretty new to this language and don't know all the bells and whistles

Do you have any experience with other languages? If so, that would be great, since this certainly isn't beginners' stuff. Otherwise, just ask and I can provide you with a working implementation to get you started. What kind of game/app do you have in mind?

[callowaysutton]

FreeBasic allows first-class procedures/arrays right?
And I've had experience coding in C/C++ and QB64, I just don't quite know all of the FreeBasic functions just yet

[badidea]

Haha yeah although that's going more into the theoreticals, I'm talking about something that is 'potentially' infinite. I liked how Badidea's concept was going (that's a nice oxymoron for u) and I'll try researching to figure out more information.

I have never made a chunk based tile game myself, so it could all be "bad ideas".

I do have another question now though, how do you know what chunks you should generate around the player at any given coordinate? Is it really as simple loading and unloading chunks less than a certain amount of distance away from the player, or would that be inneficient?

That is what I would try. Loading at a certain distance from the player. With distance that is at least greater then what is visible on the screen. But if e.g. enemies (outside the screen) should react on the presence of the player, a larger distance may be wanted.
For unloading chunks, some hysteresis is needed, distance larger than the the loading distance. If your character has a 'fever' and is slightly moving left and right (up or down) continuously, you don't want continues loading and unloading.

What should happen to enemies inside a chunk that should be unloaded is an other question.

Now going to read Paul's links...

[paul doe]

FreeBasic allows first-class procedures/arrays right?

Arrays yes, first-class functions no. FreeBasic does support function pointers, though. Just bare function pointers, not delegates.

And I've had experience coding in C/C++ and QB64, I just don't quite know all of the FreeBasic functions just yet

FreeBasic is, in general, more akin to C than C++. There's also simple but functional OOP features built-in, if you need them.

Now, since you know C++, the biggest challenge you'll face in FreeBasic is that it doesn't have any built-in data structures, nor libraries like STL to aid you, so you'll have to basically code all your data structures (sans arrays of course) from scratch. And this highlights another challenge: FreeBasic does not yet support proper templating. You can somehow fudge them through #macros, but of course it isn't the same thing.

Not that any of these will stop you, of course. Are you interested in the technique or not? What kind of game/app do you have in mind?

[marcov]

Hi, a real infinite world will be difficult. There is not enough storage space in the universe for that :-)

Not sure, it could grow from a procedural seed. I mean like a fractal for example. In any case, once sufficently grown (far before infinity), no player would be able to visit every places without the feeling of infinity, and shouldn't it be sufficent?

Ah yes, if you are not allowed you change the world (like in minecraft), an infinite world would require 0 storage, just code. (I think).

If you could calculate a tile for a very large world, even if you allow modification, you'd only have to store the diffs for the tiles that actually changed.

You could also employ techniques like e.g. Diablo does, only allow to visit the exact same location in the same session. Or e.g. forget about it if you are more than <n> tiles away.

[angros47]

Usually, to store a tile map in memory there are two possible solutions: a matrix (that is basically a standard 2d array) that is fast, and simple, but for large tilemaps require a huge amount of memory, or a quad tree. https://en.wikipedia.org/wiki/Quadtree

A quad tree can surely be implemented in FreeBasic, using a custom type and the "new" operator, and it would be more scalable, since it would allow to use tiles of different sizes (a larger tile could be filled with tiles of the same type), and only the tiles that are actually full will use memory.

If the wiki article is not clear, I can elaborate more, but a quad tree is not so intuitive to use.

[callowaysutton]

FreeBasic allows first-class procedures/arrays right?

Arrays yes, first-class functions no. FreeBasic does support function pointers, though. Just bare function pointers, not delegates.

And I've had experience coding in C/C++ and QB64, I just don't quite know all of the FreeBasic functions just yet

FreeBasic is, in general, more akin to C than C++. There's also simple but functional OOP features built-in, if you need them.

Now, since you know C++, the biggest challenge you'll face in FreeBasic is that it doesn't have any built-in data structures, nor libraries like STL to aid you, so you'll have to basically code all your data structures (sans arrays of course) from scratch. And this highlights another challenge: FreeBasic does not yet support proper templating. You can somehow fudge them through #macros, but of course it isn't the same thing.

Not that any of these will stop you, of course. Are you interested in the technique or not? What kind of game/app do you have in mind?

A 2D top down sandbox or roguelike world with coordinates that could possibly be ported into a multiplayer game is basically all. I think the hardest thing would be loading and unloading chunks and rendering since just combining a bunch of arrays into a bigger array isn't that hard, especially with Dynamic Arrays (https://www.freebasic.net/wiki/wikka.ph ... iondynamic)

[badidea]

A 2D top down sandbox or roguelike world with coordinates that could possibly be ported into a multiplayer game is basically all.

I had a look at Paul's "Dungeon Siege" pdf-link. The main message I got from that is: With a multiplayer game, things get way more complicated.

[paul doe]

...
I had a look at Paul's "Dungeon Siege" pdf-link. The main message I got from that is: With a multiplayer game, things get way more complicated.

It's the requirements (namely, a 'continuous world') that made it complicated, not so much the technique. There are some interesting workarounds for that (stated in the paper). There was another, more meaty, post-mortem of the same game that alas, I couldn't find, and it explained many of these concepts in detail. Btw, Dungeon Siege was one of the (if not the) first games that used what we now know as 'Entity-Component-System' architecture, that has become the de-facto standard for games nowadays.

...A 2D top down sandbox or roguelike world with coordinates that could possibly be ported into a multiplayer game is basically all. I think the hardest thing would be loading and unloading chunks and rendering since just combining a bunch of arrays into a bigger array isn't that hard, especially with Dynamic Arrays (https://www.freebasic.net/wiki/wikka.ph ... iondynamic)

I imagined something like that. Certainly, loading and unloading (collectively referred to as streaming) content on the fly will give you quite the headaches (because it needs to be smoking fast, not because it's particularly hard). However, if you've read the paper, you'd understand some of the challenges involved. You can try with the dynamic array approach but it does pose some challenges, too. Namely, how will you handle the extents of your world?
Angros47 also stated a cool alternative, quadtrees. These are pretty cool but only if you have (mostly) static geometry for the maps. Ultimately, the decision to use one data structure over another comes down by deciding on trade-offs, as usual.