Qbasicnews.com

I just came to think of this, while messing with the MOoRPG collision layer...


Let's say you are making a game, with a few hundred objects, that needs to be checked for collision.

First thing that comes to mind:

Which would evolve into:

Now, let's assume 10 objects.. this would mean ~100 checks.

Pretty fast... definitely acceptable...


Now, let's assume 1000 objects.. that's 1 000 000 checks.. one million...

Try this:

Takes a while, sure, might only take 0.1 seconds on your 1044GHz machine ( ), but think about it.. 0.1sec... maximum you could possibly get in your game would be 10FPS... ever played a game at 10FPS?


"I'll just use a collision layer then, and make the objects update it"
Sure.. This works for small maps, and when each object only take a small amount of memory.

Consider:
A world of 5120 x 3200 tiles, where each tile is 64x64 pixels, and you want pixel perfect collision (you do want pixel perfect collision) and p*p scrolling.

A collision layer would take 67108864000 bytes (5120*64 * 3200*64) or ~64GB

Ofcourse, this assumes 8bits per pixel, which might not be needed, you might only need passable, or not passable, and in that case a simple bitmap will suffice, and you'll end up with a colission layer of ONLY ~8GB

A bit inefficient, dont you think?


So we can't use a colission layer, nor can we scan through all the objects every frame (read: everytime you move)

So what to do..

The first thing I thought of, was:
"I'll just divide each tile, and not use pixel perfect colissions"
So, I went ahead with dividing each tile into areas of 4x4, instead of 64x64, thus I could only get colissions down to an accuracy of 16 pixels (which sucks BIG TIME, esp in mode 13h.. 16 pixels is 'half-way across the screen' )

But I went ahead with it.

The new formula would then be: 5120*4 * 3200*4

Which means 262 144 000 bytes, or 250MB
"Wow... from 64GB down to 250MB, that's quite good"

Tested it, and DAMN it sucks... "OMFG!, I wasnt even near that cliff!, WTF!, Why cant I enter the door!?!?!?!"

Ya.... So that was a crappy idea...


Then I realized...

When will the ENTIRE world be filled with objects? Or even if you shrink it to 4x4 possibe locations per tile, when?

Never... unless I plan on having 16 384 000 objects, at the same time, in the world. Which I dont (Nor do you, you hear me.. that's a shitload of objects.. don't even think about it.. dont... Or I'll beat you up... damit!)

So... How about I store all the objects in a database, with their X, Y values?

DOH!, Back to square one... but wait...


How about a combination?

A database of, lets say, the X locations, with N number of slots for location data?


Like this:
You have a map, let's say it's 10x10. You decide to have a maximum of 25 objects in total on the map at any given time.
You also decide that there can only be 7 objects on the same Y axis.

The database file now looks something like:

Great, but that doesent help us at all...

Nope... but wait.. what if, for each X position in the file we store the EXACT X and Y position, as well as any other data we might want for that object?

Ok, so the map is 10x10...

Let's say we create an Array:

"Why As String * 56?"
Hang on...

Now, to store a object, we first find out where the object is on the X axis..

Let's say this is our object:

To store it we do:

And there you go, Hans is stored, along with some data for him.


For a 10x10 map this is kind of a bad idea, but it works.

But think about the 5120x3200 world I'm using

Using the above technique, and storing:
X, Y, ID (all take 4 bytes, totaling at 12)

I need to store the exact X possition too, as I only used it tilewise, or I would end up with 327 680 X axis positions, each taking MaxObjsPerYAxis*8 bytes... a bit large, ey?

Anyways...

Storing that, and assuming 2000 objects max per Y axis, and X tile axis (not pixel axis)

I got a collision file at 117MB (5120 * 12 * 2000)

Over 100MB less then the crappy non-pixel perfect version!

And it's fast!


Think about it... To see if you have collided, you just read the X axis in your database file

A For Next loop of only 2000 objects MAX... and read their X and Y position and compare it to whatever you want...


It's fast, really really fast.. and this enables me to use up to 10240000 objects... :o




Anyways... Break it... Find the flaws and holes in it... Doooo it!.. You know you want to! If you don't I'll brag forever! *muahahaha*




Note: The code blocks are untested, and provided for better visualization only, I didn't know how to explain stuff so... Sorry about that =)

I had to read it twice to kind of understand (I don't kow alot about collison detection) but geez that's cool.

EDIT: I just noticed that my sig scrolls the screen on 800x600 does this bother anyone?

Indeed that is a much better collision detection method, but only viable with LARGE numbers of objects. The problem being, a ton of space is wasted with all those extra zeroes. A game that goes from 100kb to 100mb is a bit of a sacrifice just for a collision layer. But I guess, it works ;D

Heh... It's better then the 250MB collision layer I first tried...


And MOo went from 300MB to 150MB... so.. it's better IMO


This only works on HUGE maps, with LARGE numbers of objects.. it's a waste on anything small to medium..

Area subdivision?

Quote:Area subdivision?

That .. and depending on the type of game, you'd only have to check the objects which moved .. Dun think there'd be a game with 1000000 items moving simultaneously ..

hey who isn't happy if a small qb prog all of a sudden spits out 150 mb files onto your harddisk? i would like that... btw, that loop that produced this file of 350mb with only zeros in it, well done. blitz compressed it, i guess it only had 16kb then hehe... yeah i know collision layer...

Rel, ya, I am using area subdivision, just tried to keep the explanation simple... tried...


Marcade, no, I have to check all objects, as objects include trees etc. Because you can cut a tree down. World is dynamic.


marzecTM, Uhm, what? MOo is anything but small. And if you're talking about the last release, 276FX, it had a 250MB file, filled with chr0s. It was the divided tile collision layer, it wasnt used other then when developing. I just forgot to remove it, it didnt exactly affect the zip that much so I never thought about it.
Same with the entire Tiles folder, which is never used other then when developing.

The tiles are in Mods\MOoRPG\Data\Tiles.MOo



And really, I could go with a collision layer, at like 1.5GB, IT WORKS FOR ME!, in good 'ol C/C++ style.
C/C++: "Anything that works, no matter how innefficient, works. Move on"



marzecTM, I still don't get what you mean

hehe, nah i was just suprised when blitz showed me the code that actually created that 250mb file. i wondered what it could be used for, after reading this thread i had at least a slight idea hehe.

nm, just found it funny, cause i never saw a qb programm that operated with such big files yet. such big files that only contain 0s hehehe...

Why not try something like this(combined into one)?

1)Store the grid locations which actually have a blocker in a list, which you could clear when you loaded a new map, or REDIM if your map had more than the expected number of blockers

2)Store blockers in a "blocker heap", allocating space for a maximum number of blockers which could concievably show up on the screen at once, then dynamically loading new blocking tiles on the fly, using some form of garbage collection to deallocate blocks in the heap(or, if it's not too rough, even just purging the buffer and reloading them all when you hit a set limit). this should let you cut the blocker maps into something as small as 2x2 and still use very little memory storing them

3)creating a list of the blockers which are actually on the screen at the time from the list stored in 1) every few frames(It could be done every frame without too much of a speed decrease, but it would suck), which would be accessed when doing collision detection, rather than the full list for the 5120x3840 map

I use similar dynamic loaders and sorters in Quest for a King to let me use over 60 000 tiles and 130 objects(it's a hard limit I could erase, but it would be a waste -- even with huge fences composed of objects, I haven't come CLOSE to hitting the limit yet) on a map as long as there are fewer total tiles on the screen at once than the size of my object tile and background tile heaps. It's also virtually free, depending on how I poll for new tiles.

Let me know what you think.