## unity – Navigation algorithm to find closest point with LOS to another agent

I am trying to design an algorithm to detect the closest point where an agent has line of sight to another specified agent in 3D space and to move towards that point.

The use case would be a turn based strategy game where the AI has to move into a position where they can shoot the player’s unit. The AI agent can only move a limited distance per turn and their weapon has a limited range. They would ideally be positioned where they have line of sight to the player’s unit and they are at the max range of their weapon.

At the moment I have a nav mesh set up which can allow the AI agent to move towards arbitrary points on the map with the shortest distance using A* but I am stuck on trying to figure out the best positions to move into where they can shoot the player’s unit. Any advice?

I am using Unity Navmeshes.

Posted on Categories Articles

## algorithms – Minimize the average distance from each cities to the closest hospitals

There are n cities (1, 2, 3, …. n) and k available hospitals. k < n. We need to place hospitals into the cities. How to place these hospitals to minimize the average distance from each cities to the closest hospitals.?

Right now my thought is using dynamic programming with a 2D array of size n * k. Then I know optimal solution will be
f(n, k) = , which pump𝑘 is the position at the median of cities 𝑖+1,…,𝑛. I believe this is the right approach but I do not know how to store the location of each hospitals. Please help

Posted on Categories Articles

## object oriented – Python inheritance: how to check the closest abstract parent class?

I’m dealing with two categories of machine learning algorithms. For simplicity, let’s call them A and B.

There are multiple concrete algorithms in each category, and my goal is to implement all of them. Because of this, my initial plan was to define abstract classes `CategoryAAlgorithms` and `CategoryBAlgorithms`, and have each of them define a set of methods that must be implemented by the concrete algorithms. So far so good – these abstract classes serve as a nice template and I find that they make my project a lot more understandable.

However, after I’ve done this, I found that the abstract methods defined in `CategoryBAlgorithms` contain all the abstract methods defined in `CategoryAAlgorithms`.

To avoid code duplication, I want to have `CategoryBAlgorithms` inherit from `CategoryAAlgorithms`. However, somewhere else in my code I do the following checks:

``````# just an example
if isinstance(some_instance_of_a_concrete_algorithm, CategoryAAlgorithms):
do_some_kind_of_preprocessing()
elif isinstance(some_instance_of_a_concrete_algorithm, CategoryBAlgorithms):
do_some_other_kind_of_preprocessing()
``````

This means that, if I do the inheritance, then for a concrete algorithm from category B, both if statements would be true.

Is there a way for me to get around this issue? My initial thought was to check for the closest abstract parent, but I don’t think this is a clean solution, so I welcome other ideas.

Thanks in advance.

Posted on Categories Articles

## hlsl – How to raycast octree for closest leaf node?

So I need to raycast a octree for closest leaf node as efficient as possible. I will be doing it on compute shader (hlsl), but I think it doesn’t matter because first I need to understand the approach and math behind this process in general.

My struct looks like this:

``````struct OctreeNode
{
uint  size; // size of cubic node

uint posX; // center of node
uint posY; // center of node
uint posZ; // center of node

uint childExists;
uint isLeaf;
uint isChild;

uint parentIndex; //Parent node index in structured buffer
uint minchildIndex; // Node child min index in structured buffer (+1 is next child, etc)
uint index; //Index in structured buffer
};
``````

Octree is rather big, so I guess I can’t afford to raycast everything and then compare distances. I have been looking into https://stackoverflow.com/questions/6281415/octree-raycasting-raytracing-best-ray-leaf-intersection-without-recursion , but I do not understand the answer (especially HLSL one with `hitbox` what is unknow thing).

Any hints, code, directions highly appreciated.

## list manipulation – Connecting the closest points on circles with a line

Suppose I have the function `f(c_, z_) := z^2 + c` and the following collection of circles in the plane. This is a simple example with only three circles, disjoint and not nested, and lying on the real line.

``````Show(Table(Graphics(Line(ReIm(Nest(f(-1.755, #) &, Map(comp, CirclePoints({0, 0}, 0.1, 1000)), i)))), {i, 0, 2}))
``````

Given one circle, I would like to connect it to the closest circle (that isn’t itself) by the shortest possible line. So in this example the lines would be the segments of the real line between the closest points of the circles. The following code does this manually.

Take `comp({x_, y_}) := x + y*I` and then the following gives the desired picture.

``````Graphics(Line(
ReIm({Nest(f(-1.755, #) &,
Map(comp, CirclePoints({0, 0}, 0.1, 1000)), 0),
Map(comp,
Table(BezierFunction({Map(ReIm,
Nest(f(-1.755, #) &,
Map(comp, CirclePoints({0, 0}, 0.1, 1000)), 0))((750)),
Map(ReIm,
Nest(f(-1.755, #) &,
Map(comp, CirclePoints({0, 0}, 0.1, 1000)), 1))((750))})(
s), {s, 0, 1, 0.001})),
Nest(f(-1.755, #) &, Map(comp, CirclePoints({0, 0}, 0.1, 1000)),
1), Nest(f(-1.755, #) &,
Map(comp, CirclePoints({0, 0}, 0.1, 1000)), 2),
Map(comp,
Table(BezierFunction({Map(ReIm,
Nest(f(-1.755, #) &,
Map(comp, CirclePoints({0, 0}, 0.1, 1000)), 0))((250)),
Map(ReIm,
Nest(f(-1.755, #) &,
Map(comp, CirclePoints({0, 0}, 0.1, 1000)), 2))((750))})(
s), {s, 0, 1, 0.001}))})))
``````

This is messy but it works. However for more circles this will become very tedious to implement. Is there a quicker way to do this? I would still like to get the points along the connecting lines for future calculations. Also, perhaps more difficult, what if the parameter `c` for `f(c,z)` is complex so the lines are no longer in a straight line?

Posted on Categories Articles

## expected value – Poisson Point Process Closest Point

Suppose we have a Poisson point process, with intensity $$lambda$$. I want to prove that the expected distance from the origin and the closest Poisson point is $$frac{1}{2sqrtlambda}$$ when in two dimensions. Now, my thinking is this:
The probability that there is no Poisson point within radius $$r$$ is $$P(X(B)=0)=e^{-lambdapi r^2}$$.
So the probability that there is at least one Poisson point is $$1-e^{-lambdapi r^2}$$. This is where I’m stuck. I want to find the expected distance, but I’m not sure how to continue in a way that doesn’t invoke the PDF for the distance and then using integration to find the expected distance. Is there any other way to prove this?

Posted on Categories Articles

## python 3.x – How to get duplicates and assume the closest numbers in the list as a duplicate in pyhon?

I have a list of tuple and want to get duplicates. The closest numbers (for tuples) in the list will also be counted as a duplicate. Let me explain with an example:

``````myList = ((1,2), (4,7), (30,41), (31,40), (31,41), (30,40), (30,40), (3,9),
(4,10), (28,39), (30,40), (32,44),(90,4))
``````

If the distances btw tuples are less than 10, one of these tuples will be copied and append in a list.

``````(1,2) ,(4,7),(3,9), (4,10) ---> abs(1-4) < 10 and abs(2-7) < 10 then it will be:
((4,7), (4,7), .....) and so on.
``````

the list with duplicates should be so:

``````#result = ((4,10), (4,10), (4,10), (4,10), (32,44), (32,44), (32,44), (32,44), (32,44),
(32,44), (32,44), (32,44), (90,4))

print(getDupWithCount(result)) #gives me :
#{(1, 2): 4, (30, 41): 13, (31, 40): 13, (31, 41): 13,
#(30, 40): 39, (28, 39): 13, (32, 44): 13, (90, 4): 12,
#(4, 7): 12, (3, 9): 12, (4, 10): 12}
But print of the result should like this:
#((4,10):4, (32,44):8, (90,4):1)
``````

My code:

``````for a in new_ml:
while(j < len(new_ml)-1):
while(i < len(new_ml)-1):
if(abs(new_ml(j)(0) - new_ml(i+1)(0)) <= 10 and abs(new_ml(j)(1) - new_ml(i+1)(1)) <= 10):
list_a.append(new_ml(j)(0))
list_b.append(new_ml(j)(1))
else:
list_a.append(new_ml(i+1)(0))
list_b.append(new_ml(i+1)(1))
i += 1
list_a.append(new_ml(j)(0))
list_b.append(new_ml(j)(1))
j += 1
i = 0
#print(list(zip(list_a,list_b)))
result = list(zip(list_a,list_b))

def getDupWithCount(listOfEl):
dictOfEl = dict()
for elem in listOfEl:
if elem in dictOfEl:
dictOfEl(elem) += 1
else:
dictOfEl(elem) = 1

dictOfEl = { key:value for key, value in dictOfEl.items() if value > 1}
return dictOfEl
``````

Posted on Categories Articles

## collision detection – How can I find the closest point between an oriented bounding box and a capsule?

My capsule is defined by a center position with a radius and length. I have capsule/capsule, sphere/sphere, sphere/capsule, sphere/obb, obb/obb, and sphere/triangle collision working, but I cannot figure out how to do capsule/obb.

I know how to find the closest point on an obb to another point, the closest point on a line to another point, and the closest point between two lines.

Posted on Categories Articles

## algorithms – Why sort the points acc to y coordinates in closest point divide and conquer method?

The divide and conquer strategy for closest point problem sorts the points according to x coordinates so that the median could be found. But what does sorting the strip (strip array contains all the points which are at most d perpendicular distance apart from the median line where d is the minimum distance till now) according to the y coordinates serve any purpose? Is there something that cannot be done by the already x coordinate sorted array?

Link for reference https://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html#anal

Posted on Categories Articles

## python – Can I optimize two for loops that look for the closest zip code based on lat/lon?

I am new to python and I had the task to find the US zip code based on latitude and longitude. After messing with arcgis I realized that this was giving me empty values for certain locations. I ended up coding something that accomplishes my task by taking a dataset containing all US codes and using Euclidean distance to determine the closest zip code based on their lat/lon. However, this takes approximately 1.3 seconds on average to compute which for my nearly million records will take a while as a need a zip code for each entry. I looked that vectorization is a thing on python to speed up tasks. But, I cannot find a way to apply it to my code. Here is my code and any feedback would be appreciated:

``````for j in range(len(myFile)):
p1=0
p1=0
point1 = np.array((myFile("Latitude")(j), myFile("Longitude")(j)))  # This is the reference point
i = 0
resultZip = str(usZips("Zip")(0))
dist = np.linalg.norm(point1 - np.array((float(usZips("Latitude")(0)), float(usZips("Longitude")(0)))))
for i in range(0, len(usZips)):
lat = float(usZips("Latitude")(i))
lon = float(usZips("Longitude")(i))
point2 = np.array((lat, lon))  # This will serve as the comparison from the dataset
temp = np.linalg.norm(point1 - point2)
if (temp <= dist):  # IF the temp euclidean distance is lower than the alread set it will:
dist = temp  # set the new distance to temp and...
resultZip = str(usZips("Zip")(i))  # will save the zip that has the same index as the new temp
# p1=float(myFile("Latitude")(58435))
# p2=float(myFile("Longitude")(58435))
i += 1
``````

I am aware Google also has a reverse geocoder API but it has a request limit per day.
The file called `myFile` is a csv file with the attributes userId, latitude, longitude, timestamp with about a million entries. The file usZips is public dataset with information about the city, lat, lon, zip and timezone with about 43k records of zips across the US.