Grid Structure

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
Kadoba
Party member
Posts: 399
Joined: Mon Jan 10, 2011 8:25 am
Location: Oklahoma

Grid Structure

Post by Kadoba » Mon Nov 07, 2011 9:00 pm

I find myself messing with 2d data structures a lot so I decided to make a reusable grid class. It turned out to be really helpful for me so I thought I would spruce it up and release it. There's no documentation but using it is fairly straightforward. I've made a little demo showing how to do different operations on it.
Attachments
Grid.love
(2.45 KiB) Downloaded 222 times
Last edited by Kadoba on Tue Nov 08, 2011 7:21 pm, edited 2 times in total.

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

Re: Grid Structure

Post by Taehl » Mon Nov 07, 2011 9:30 pm

Looks pretty slick! Your line-making algorithm is a little odd, though. I'd suggest switching to Bresenham's line algorithm, but you seem to want the "don't plot diagonals, only plot up/down or left/right" thing.
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
Kadoba
Party member
Posts: 399
Joined: Mon Jan 10, 2011 8:25 am
Location: Oklahoma

Re: Grid Structure

Post by Kadoba » Mon Nov 07, 2011 9:54 pm

You can make the line travel diagonally by making the fifth parameter in grid:line true which makes it act just like Bresenham's. The algorithm I used is essentially a compact Bresenham's but altered so you can have a choice of non-diagonal movement.

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

Re: Grid Structure

Post by Taehl » Tue Nov 08, 2011 12:32 am

If it's Bresenham's, how do you end up with the last pixel /always/ being vertically off-set if the line isn't perfectly horizontal or vertical? (Example: Make a long horizontal line which goes up by just one pixel. Instead of switching half-way through the line, which would be the correct rasterization, Grid will produce an "L" shape)
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
Kadoba
Party member
Posts: 399
Joined: Mon Jan 10, 2011 8:25 am
Location: Oklahoma

Re: Grid Structure

Post by Kadoba » Tue Nov 08, 2011 3:46 am

You're talking about the yellow line following the mouse in the demo, right? The line algorithm has two modes. The default mode is "non-diagonal" which is what the yellow line in the demo draws with. This is exactly like Bresenham's except it doesn't allow the line to walk diagonally. The other mode is "diagonal" mode or exactly how you would expect a Bresenham's algorithm to draw. All you have to do to make the line be able to traverse diagonally is just make the fifth parameter true when you call grid.line().

Here's the demo but with the yellow line set to diagonal mode:
Grid.love
(2.35 KiB) Downloaded 67 times
All I did was change the grid.line() call in main.lua from this:

Code: Select all

for x,y,v in grid:line(50,35, math.ceil(love.mouse.getX()/size), math.ceil(love.mouse.getY()/size)) do
to this:

Code: Select all

for x,y,v in grid:line(50,35, math.ceil(love.mouse.getX()/size), math.ceil(love.mouse.getY()/size), true) do
I guess I should make diagonal mode the default since that's how most people expect a line to be drawn.

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

Re: Grid Structure

Post by Taehl » Tue Nov 08, 2011 5:52 am

I understand what you said before. What I'm trying to point out is that your non-diagonal lines don't rasterize correctly. Take a look:
Image
The top line is how your function currently rasterizes lines. The bottom is a more correct rasterization.
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
miko
Party member
Posts: 409
Joined: Fri Nov 26, 2010 2:25 pm
Location: PL

Re: Grid Structure

Post by miko » Tue Nov 08, 2011 9:10 am

Taehl wrote:I understand what you said before. What I'm trying to point out is that your non-diagonal lines don't rasterize correctly. Take a look:
Image
The top line is how your function currently rasterizes lines. The bottom is a more correct rasterization.
I bet this is because the original algorithm assumes that the pixel centers have integer coordinates. So, to calculate the error in love2d, you need to offset the coordinates by 50% of the cell size.
My lovely code lives at GitHub: http://github.com/miko/Love2d-samples

User avatar
Kadoba
Party member
Posts: 399
Joined: Mon Jan 10, 2011 8:25 am
Location: Oklahoma

Re: Grid Structure

Post by Kadoba » Tue Nov 08, 2011 7:28 pm

:crazy: Sorry I got confused there. The reason why that was happening wasn't due to integers but I think I've fixed it now. I've reuploaded the file in my original post. I've also made the default line mode diagonal. In the demo you can switch line modes by right clicking now.

Thanks for pointing this out so I could fix it.

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

Re: Grid Structure

Post by Taehl » Tue Nov 08, 2011 10:59 pm

No problem. So, what kind of a game are you going to build with this?
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
Ellohir
Party member
Posts: 235
Joined: Sat Oct 22, 2011 11:12 pm

Re: Grid Structure

Post by Ellohir » Tue Nov 08, 2011 11:10 pm

I think this is a bug, isn't it?
Attachments
bug.PNG
bug.PNG (11.17 KiB) Viewed 1540 times

Post Reply

Who is online

Users browsing this forum: No registered users and 19 guests