Picking cells which form a completed line between to 2d grid cells

Question

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:

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.

Answer 1

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.

Answer 2

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.