Fizz X

[ivan]

Here is one tutorial:
http://2dengine.com/doc_1_3_10/gs_fsm.html



Attached is a Love2d version of the tutorial.

[Taehl]

Hello again. It's nice to see how this project has matured. I never imagined that my dinky little Fizz would end up so polished.

Did you use a tutorial to implement quadtree partitioning in Lua (and if so, could you please link me to it)? Or, if you made it yourself, would you please explain how it works?

[ivan]

Thanks Taehl!
Actually, I was in the process of refactoring the quadtree code because the code is not very good.
It's based on a book called "Realtime Collision Detection" by Erickson.
For starters I'd like to say that quadrees are slow and are not the ideal solution for 2D games.

The basic idea is that you start with a large square and divide it into four smaller squares (quadrants).
Then you take each one of the four smaller squares and divide them into four smaller squares and so on.
Now you have a nice tree where your objects (bounding boxes) can be inserted.
Larger objects are inserted in larger quadrants (higher up the tree) and smaller objects are inserted in smaller quadrants (deeper in the tree).
Let's say that we have an object O inserted in some square Q on the tree.
To check for collisions you iterate:
1.all objects inserted in square Q
2.all objects inserted in children squares of Q
3.all objects inserted in parent squares of Q
That's the basic idea behind quadtrees.

Then tricky part comes in.
So, what happens if you have an object that overlaps two quadrants?
The easy answer is: insert it in its parent square.
That sort of works... but it's not very efficient because a small object may be positioned so that it overlaps all four quadrants in the root square.
So it will end up in the root square, regardless of its small size.
In Fizz, we use a "loose" quadtree where the squares are doubled in size which makes them overlap.
When the squares in the tree overlap you no longer have the "straddling" between quadrants problem.
This way, you know ahead of time at what depth an object will be inserted.
If it's 30x30 it will be inserted deeper in the tree, if it's 1000x1000 it will be inserted higher, regardless of its position.
If your tree is pre-allocated you can do some pretty cool optimizations too like resolving the in which quadrant an object will be inserted.
The main disadvantage is if your tree becomes too deep it will be slow to iterate.

The nice thing about quadtrees is that you can always expand the tree up or down to support dynamically-sized worlds.

[bartbes]

So, what happens if you have an object that overlaps two quadrants?
The easy answer is: insert it in its parent square.

I've only ever heard of the version where you insert it in every quadrant it overlaps with, while that might seem like the same thing, it's not, because if a tiny object is in the exact centre of the world, you'd put it in 4 boxes at the bottom of the tree, meaning only objects close to the edges are only ever eligible for collision with it.

[Roland_Yonaba]

For starters I'd like to say that quadrees are slow and are not the ideal solution for 2D games.

I've had the same opinion, the first time I dabbed with them. I just sticked to spatialhashes.

[ivan]

I've only ever heard of the version where you insert it in every quadrant it overlaps with, while that might seem like the same thing, it's not, because if a tiny object is in the exact centre of the world, you'd put it in 4 boxes at the bottom of the tree, meaning only objects close to the edges are only ever eligible for collision with it.

I see what you're saying. Yes, your approach would work well if the tree doesn't change much or when the tree is pre-allocated.

PS. Another thing I forgot to mention about "loose" quadtrees is that queries are a little more complicated because the quadrants overlap.

I've had the same opinion, the first time I dabbed with them. I just sticked to spatialhashes.

A quadtree is kind of like a grid too, just hierarchical. Imagine dividing a given space into several grids with different cell sizes.

[ivan]

The new version of Fizz is out.
Fixes some issues and shows a better way to implement jumping.

[yifanes]

very nice

[ivan]

Very crude HTML5/JS port of the basic functionality of Fizz:
http://2dengine.com/doc/tutorials/html5/index.html
Based on the tutorial:
http://2dengine.com/doc/gs_collision.html

[airstruck]

http://2dengine.com/doc/gs_collision.html

Really enjoyed reading that, nice work.