2
\$\begingroup\$

I'm using Bresenham's line algorithm to calculate a "line" of cells between a start and end point on a 2D tile grid.

However, I'm using this during terrain generation to create a visible pathway, which means I need every cell to have at least one shared border with a neighbor.

This shows how the line algorithm is picking cells:

enter image description here

Yet if you imagine this as a road, there's no way to drive from one "segment" to the next.

How can I calculate a line that doesn't "jump" like this?

I've thought about using pathfinding or raycasting but they both feel like overkill because they worry about things I don't need here. I won't have obstacles to route around and I don't care about calculating ray intersections.

\$\endgroup\$
  • 1
    \$\begingroup\$ If you can only make orthogonal (n,s,e,w) steps you can think about the problem as two separate loops, over evenly spaced vertical and horizontal steps. If you merge those two loops together it will interleave the vertical and horizontal steps and give you what you want (I think). I have an explanation and sample code here \$\endgroup\$ – amitp Oct 1 '16 at 16:53
1
\$\begingroup\$

Lets start by defining an array 'p'. This array will contain booleans and will tell us if there is a path at a specific point on the terrain. The idea is that you will perform Bresenham's algorithm on that Boolean array and then you will create an "outline" for that line. Then you will add the line and the outline together, making the original line thicker.

Also another thing you could do is modify the line algorithm and make it so that it gives a thicker line.

\$\endgroup\$
0
\$\begingroup\$

Draw bresenham's line, adding the modified cells to a list, with the same number of "checked" flags. For each cell in the list, flag it, check how many unflagged neighbors it has, if it has 0 and is not the final cell in the array, then add a 4-connected cell between it and the next unmarked cell in the list, and continue.

This is based on image processing techniques in which you may outline or fill an area of pixels with a given color. Much like bresenham's you'll simply be filling the cells with a new map value instead.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.