Jump to content
  • Advertisement
Sign in to follow this  
Cornstalks

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!