Fizz X

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
ivan
Party member
Posts: 1137
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Fizz X

Post by ivan » Mon Dec 08, 2014 12:54 pm

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

Image

Attached is a Love2d version of the tutorial.
Attachments
platform.love
(11.35 KiB) Downloaded 107 times

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

Re: Fizz X

Post by Taehl » Sun Jan 11, 2015 8:45 pm

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+.

User avatar
ivan
Party member
Posts: 1137
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Fizz X

Post by ivan » Mon Jan 12, 2015 11:31 am

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.

User avatar
bartbes
Sex machine
Posts: 4867
Joined: Fri Aug 29, 2008 10:35 am
Location: The Netherlands
Contact:

Re: Fizz X

Post by bartbes » Mon Jan 12, 2015 12:57 pm

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.
Cowardly acts and the eating of birds must not be the deeds of a Hero of Storms.

User avatar
Roland_Yonaba
Inner party member
Posts: 1559
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Fizz X

Post by Roland_Yonaba » Mon Jan 12, 2015 4:13 pm

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.

User avatar
ivan
Party member
Posts: 1137
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Fizz X

Post by ivan » Sat Jan 17, 2015 4:41 pm

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.

User avatar
ivan
Party member
Posts: 1137
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Fizz X

Post by ivan » Sun Mar 08, 2015 1:48 pm

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

Post by yifanes » Fri Apr 17, 2015 9:51 am

very nice

User avatar
ivan
Party member
Posts: 1137
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Fizz X

Post by ivan » Sat Jun 27, 2015 10:54 am

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

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: Fizz X

Post by airstruck » Sat Jun 27, 2015 8:25 pm

Really enjoyed reading that, nice work.

Post Reply

Who is online

Users browsing this forum: Bing [Bot] and 7 guests