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

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

## 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 on other sites

As a simple quick solution I would use recursion so each node could test itself to certain state and then progress or skip but thats less an alforithm

Edited by Shaarigan

##### 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 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 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 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 on other sites

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

Use the Midpoint Circle Algorithm to trace a line (bresenhamn's algorithm) from the center to each point on the edge circle. Stop if you find a wall.

Edited by desdemian

##### 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 _tempNodes = new GridNode[maxSize];
var _tempNodesCount = 0;
var _openSet = new HashSet<GridNode>();

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

//get border nodes

//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];
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 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

1. 1
2. 2
Rutin
17
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633735
• Total Posts
3013596
×