## Fizz X

ivan
Party member
Posts: 1363
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

### Re: Fizz X

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

Attached is a Love2d version of the tutorial.
Attachments
platform.love

Taehl
Dreaming in associative arrays
Posts: 1024
Joined: Mon Jan 11, 2010 5:07 am
Location: CA, USA
Contact:

### Re: Fizz X

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?
Earliest Love2D supporter who can't Love anymore. Let me disable pixel shaders if I don't use them, dammit!
Lenovo Thinkpad X60 Tablet, built like a tank. But not fancy enough for Love2D 0.10.0+.

ivan
Party member
Posts: 1363
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

### Re: Fizz X

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
Sex machine
Posts: 4943
Joined: Fri Aug 29, 2008 10:35 am
Location: The Netherlands
Contact:

### Re: Fizz X

ivan wrote: 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
Inner party member
Posts: 1562
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: Fizz X

ivan wrote: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
Party member
Posts: 1363
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

### Re: Fizz X

bartbes wrote: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
Party member
Posts: 1363
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

### Re: Fizz X

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

yifanes
Prole
Posts: 2
Joined: Fri Apr 17, 2015 9:47 am

### Re: Fizz X

very nice

ivan
Party member
Posts: 1363
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

### Re: Fizz X

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
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

### Re: Fizz X

Really enjoyed reading that, nice work.

### Who is online

Users browsing this forum: No registered users and 2 guests