Motion planning without a graph across an infinite plane
An object is positioned at A and wants to move to B. I want to calculate a movement vector there that doesn't move within the distance D of the to-be-avoided points in array C.
So if the move vector (B-A) normalized and multiplied with the objects speed would bring it within D of any point in C the vector is rotated so that it doesn't.
This is in two dimensions. Also, if this operation has a name, please make a comment or edit this question yourself as I had no idea of what to call it.
Also, my first instinct was to divide the active area into nodes and run a A* but I want to try the mathematical approach on this one, a few experiments with flocking gives me the impression that it can be done.
Update (from comments): This image is very close to the solution I want:
Assuming we start at the point to the left, we start turning right towards the goal (the other point), we detect a wall on the right so we stop turning and move forward. The wall is gone so we are allowed to start turning towards the goal again, and so on. I know this may cause the object to not get there at all, but I want to define a behavior, not necessarily a solution, if you know what I mean.
Update2: Translating the active area into a set of nodes might prove inefficient. A* and other heuristic graph traversal algorithms are great for low dimensional problems. But the area I want to move across is infinite in size and only has a handful of obstacles scattered across it. The nodes themselves, or rather the potential positions, are infinitely small. This could of course be optimized with a quad tree of some sort but I have a feeling simple movement vectors that are in some way rotated and interpolated can solve this as well.
Also on the page you linked to in your answer is a pretty good discussion of steering behaviours in general.
In particular, look at his pages for containment and path following for good examples.
- Isn't there any more efficient solution for the CodeForces 919-B/Perfect Number question?
- What's the difference between O(n) and O(n+n^1/2) in algorithm?
- Understanding dynamic programming timeouts with 2 different solutions
- ColdFusion - What's an efficient way to search an array of structs?
- Bubble sort does not sort as expected
- DirectoryInfo.EnumerateFiles(...) causes UnauthorizedAccessException (and other exceptions)
- How can I find the number of concordant/discordant pairs for a given cell in Google Sheets?
- Fastest algorithm for filling overlapping rectangles of pixels
- How to sort with incomplete ordering?
- Fast CRC algorithm?
- Extract the closest two numbers that multiply to create a given number
- Best algorithm for delete duplicates in array of strings
- Understanding the Time Complexity Difference of Two Ways to Generate Subsets
- Online algorithm for calculating standard deviation of counts
- Calculate Time Remaining
- Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
- Search Algorithm to find the k lowest values in a list (selection algorithm/problem)
- While finding count of points inside some shape using KD-Tree, do we need to check areas intersection, or just compare depth-appropriate properties?
- How to store items in the LIFO stack in a cache-friendly manner?
- What is the time complexity of heapq.nlargest?
- Shell Sort not Swapping Elements Correctly
- Linear time algorithm for computing radius of membership hyper-sphere
- How can I check Hamming Weight without converting to binary?
- Efficient Merge sort implementation in python
- algorithm to detect pools of 0s in a matrix
- how can i make my sklearn prediction model better?
- Is O(log n) always faster than O(n)
- How can I build a directory tree from a list of paths?
- Word Hunt DFS Algorithm Not Finding Optimal Solution
- How to get the first value greater than x in a range with segment tree