Sign in to follow this  
Crayz92

Getting all points of a grid within radius, how can I ignore nodes behind a "wall"?

Recommended Posts

Here's the function I'm using to grab all nodes within the radius of center point x0,z0

int r2 = radius * radius;
nodeCount = 0;

for (int x = 0; x <= radius; x++)
{
    for (int z = 0; z <= radius; z++)
    {
        if (x * x + z * z <= r2)
        {
            _nodes[nodeCount] = nodes[centerX - x, centerZ + z]; //top left
            nodeCount++;
            _nodes[nodeCount] = nodes[centerX + x, centerZ + z]; //top right
            nodeCount++;
            _nodes[nodeCount] = nodes[centerX - x, centerZ - z]; //bottom left
            nodeCount++;
            _nodes[nodeCount] = nodes[centerX + x, centerZ - z]; //bottom right
            nodeCount++;
        }
    }
}

This finds nodes in one corner of the circle and flips x,z values to get the symmetrical nodes, it will produce this:

http://puu.sh/sGK1I/9f772e3d53.jpg

 

Is there another algorithm that can start in the center and stop progressing in a direction if a rule is met?  For instance, if one of the nodes is tagged as Wall, ideally the returned node collection would then look like this:

http://puu.sh/sGL9d/a62072abda.jpg

Edited by Crayz92

Share this post


Link to post
Share on other sites

Is there another algorithm that can start in the center and stop progressing in a direction if a rule is met?


Just to clarify, what do you mean by "direction" because I think you mean that you do not want to add nodes which "share" the same line of sight as the obstruction and are further away but your drawing shows something different.

Share this post


Link to post
Share on other sites

 

Is there another algorithm that can start in the center and stop progressing in a direction if a rule is met?


Just to clarify, what do you mean by "direction" because I think you mean that you do not want to add nodes which "share" the same line of sight as the obstruction and are further away but your drawing shows something different.

 

 

Woops, my drawing was off.  It should've been like this:

http://puu.sh/sHlnJ/39f2c7191d.jpg - here's a drawing from a different center point http://puu.sh/sHlOM/6be0f49703.jpg

Share this post


Link to post
Share on other sites
Another few things you might want to clarify:

(1) What is really the desired pattern? The two images in your last post show entirely different, contradicting things. The first one culls everything behind a line perpendicular to line of sight from the center, starting at the red block. The second one culls everything behind lines parallel to the block's corners. Is what you really want to achieve not maybe something like cull against its silhouette, much like casting a shadow? Or what is it you want?

(2) Do nodes have a volume (or at least, a diameter)? If they don't, and nodes (not the red block) work as blocker, then your culling attempts will be ill-fated since you will cull zero nodes.

(3) Your code looks wrong. You're overwriting the same value in _nodes three times, then advance the index by 4. That's only the last node realized, and 3 indeterminate values. A +1/+2/+3 is missing inside the brackets.

Share this post


Link to post
Share on other sites

Another few things you might want to clarify:

(1) What is really the desired pattern? The two images in your last post show entirely different, contradicting things. The first one culls everything behind a line perpendicular to line of sight from the center, starting at the red block. The second one culls everything behind lines parallel to the block's corners. Is what you really want to achieve not maybe something like cull against its silhouette, much like casting a shadow? Or what is it you want?

(2) Do nodes have a volume (or at least, a diameter)? If they don't, and nodes (not the red block) work as blocker, then your culling attempts will be ill-fated since you will cull zero nodes.

(3) Your code looks wrong. You're overwriting the same value in _nodes three times, then advance the index by 4. That's only the last node realized, and 3 indeterminate values. A +1/+2/+3 is missing inside the brackets.

 

Okay, so I should have thought this through a little bit more before posting :wacko:

 

The ideal the pattern would be like casting a shadow assuming the center point is a 360 degree light source, and "walls" block light: http://puu.sh/sHrzm/f455240dbe.png

 

In this drawing the green dot is the center, red dots are monsters that can be affected by the AoE, white dots are monsters that cannot be affected.  The nodes in the areas where monsters cannot be affected should not be included in the array that this function returns.

 

As far as the nodes go, each node is situated on a 2d plane (x,z), and have a center origin with a fixed width & height.  Nodes are flagged as either Walkable or Wall, you can see here that red nodes are flagged as Wall and the gray nodes (hard to see) are Walkable.  The larger gray grid texture on the plane has no relation.  http://puu.sh/sHqXa/be918264e5.png

 

I've updated the code, thanks :)

Share this post


Link to post
Share on other sites


Here's an idea, going from the center to the edges:

Use the Midpoint Circle Algorithm to trace a line (<a data-ipb="nomediaparse" data-cke-saved-href="https://en.wikipedia.org/wiki/Bresenham" href="https://en.wikipedia.org/wiki/Bresenham" s_line_algorithm"="">bresenhamn's algorithm) from the center to each point on the edge circle. Stop if you find a wall.

 

This works! However there's 2 issues rooting from the lines being "Pixel Perfect".  First issue, whenever a line is built from the center point to an outer point, some of the nodes are duplicates from a previous time a line was built.  Preventing duplicates hurts performance a bit, but it might be manageable by checking for duplicates with a HashSet

The other problem is that some nodes are missed entirely.  See here:

http://puu.sh/sHNoG/6760862080.jpg

 

Here's the code I've got so far:

public void GetNodesInRadiusMinusWalls(int x0, int z0, int radius, ref GridNode[] _nodes, ref int nodeCount)
{
    //assign some local vars
    var maxSize = Mathf.CeilToInt(radius * radius * Mathf.Pi);
    var _tempNodes = new GridNode[maxSize];
    var _tempNodesCount = 0;
    var _openSet = new HashSet<GridNode>();

    //set active node count to 0
    nodeCount = 0;

    //get border nodes
    GetRadiusBorderNodes(x0, z0, radius, ref _tempNodes, ref _tempNodesCount);

    //iterate through all bordering nodes
    for (int i = 0; i < _tempNodesCount; i++)
    {
        int x1 = _tempNodes[i].x;
        int z1 = _tempNodes[i].z;

        //line interpolation function found here:
        //http://www.redblobgames.com/grids/line-drawing.html
        int len = Mathf.Max(Mathf.Abs(x1 - x0), Mathf.Abs(z1 - z0));

        for (int j = 0; j < len; j++)
        {
            float t = (float)j / len;
            int x = Mathf.RoundToInt(x0 * (1.0f - t) + x1 * t);
            int z = Mathf.RoundToInt(z0 * (1.0f - t) + z1 * t);

            //break if we hit a wall
            if (nodes[x, z].nodeType == NodeType.Wall)
                break;

            //HashSet is faster than list and recursive array iteration
            if (!_openSet.Contains(nodes[x,z]))
            {
                _nodes[nodeCount] = nodes[x, z];
                _openSet.Add(nodes[x, z]);
                nodeCount++;
            }
        }
    }
}

Edit: Rather than using a HashSet I store whether a node is opened within the class itself, this pretty much resolves the performance issue.

//if (!_openSet.Contains(nodes[x,z]))
if(!nodes[x,z].opened)
{
    nodes[x,z].opened = true;
    _nodes[nodeCount] = nodes[x, z];
    nodeCount++;
}

When everything is finished I go back over the opened nodes and set the opened value back to false

Edited by Crayz92

Share this post


Link to post
Share on other sites

Well I think I got this figured out.  To solve the issue of some nodes being missed entirely I instead used the anti-aliased line algorithm found here:

http://members.chello.at/~easyfilter/bresenham.html

 

It just padded the line a bit so nothing would be missed.  Having already-visited nodes marked as "opened" prevents mass duplicates and saves a ton of performance. 

 

100,000 iterations at the maximum allowed radius took about 7,700ms, so speed is quite good!

 

In action: https://vid.me/ctlF

 

Thanks for the replies everybody

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this