# Going from a line wall to a grid wall

This topic is 3993 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

So I've been working on my A* algorithm for awhile, and now I think it's time that I move into the 360° world. I think I've thought of a good way to do it all (I would explain it but it's hard for me to do so in an understandable way). The only problem is that I need to convert all my walls into walls on a grid (look at the picture). Red = Wall (in 360° world) Gray tile = Wall (in grid world) White tile = Open tile I have no idea how to go from the red lines to the gray tiles though. I've thought of using the lines' slopes, but that wouldn't work for vertical lines. I've thought of another method, but I don't think it's very good (I don't even know if it would work). I would iterate through all the lines and cast them onto the grid (but I'd only update the dynamic lines; static lines wouldn't need updating). This is an example of the one method I've thought of (and I think it could be much better).
// For this example, 1 unit will be the length of 1 tile
float x1, y1, x2, y2; // let these be the endpoints of the line

int distance = int(abs(y2 - y1) + abs(x2 - x1)); // the amount of tiles in between the two points in the Manhattan grid style

float dx = (x2 - x1) / distance; // the change in x's
float dy = (y2 - y1) / distance; //  the change in y's

float currentX = x1;
float currentY = y1;

for (int a = 0; a <= distance; a++)
{
grid[int(currentX)][int(currentY)].status = wall;
currentX += dx;
currentY += dy;
}


I'd be using the grid to perform my A* search. If there is a better way to do this, please let me know and help me out.

##### Share on other sites
Check intersections on wall and vertical lines, and on wall and horizontal lines. Mark each empty tile that has at least one if it's sides with an intersection as a wall tile. I think it should work.

##### Share on other sites
You might also consider using a 2D variation of 3D-DDA (three-dimensional digital differential analyzer). Just in case you're not familiar with this algorithm, I'll also mention that it's not as complicated as it sounds :)

Anyway, I think it should be perfect for what you're wanting. If however you want to go Jaiminho's route and check intersections, I would perform segment vs. AABB tests on the cells rather than line-line tests. Now that I think about it, the intersection method would probably be easier to code than 2D-DDA, and should give the same results.

There's also Bresenham, but it has different characteristics than the above methods, and probably isn't the best solution in this case.

##### Share on other sites
Just run a line drawing algorithm. This one http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm gives you all the squares the line touches.

• 10
• 17
• 9
• 14
• 41
• ### Forum Statistics

• Total Topics
631067
• Total Posts
2997734
×