Grid Structure

[Kadoba]

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.

[Taehl]

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.

[Kadoba]

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]

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)

[Kadoba]

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

[Taehl]

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.

[miko]

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.

[Kadoba]

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]

No problem. So, what kind of a game are you going to build with this?

[Ellohir]

I think this is a bug, isn't it?