## Grid Structure

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

### Grid Structure

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
Last edited by Kadoba on Tue Nov 08, 2011 7:21 pm, edited 2 times in total.

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

### Re: Grid Structure

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

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

### Re: Grid Structure

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.

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

### Re: Grid Structure

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

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

### Re: Grid Structure

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

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

### Re: Grid Structure

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:

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

miko
Party member
Posts: 409
Joined: Fri Nov 26, 2010 2:25 pm
Location: PL

### Re: Grid Structure

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:

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

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

### Re: Grid Structure

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.

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

### Re: Grid Structure

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

Ellohir
Party member
Posts: 235
Joined: Sat Oct 22, 2011 11:12 pm

### Re: Grid Structure

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

### Who is online

Users browsing this forum: No registered users and 19 guests