How to use the A * path search algorithm on a grid without a two-dimensional plane?

Question

How can I implement the A * algorithm on a brushless 2D plane without nodes or cells? I need an object to maneuver around a relatively large number of static and moving obstacles on the way to the goal. My current implementation is to create eight points around an object and treat them as the centers of imaginary adjacent squares, which could be a potential position for the object. Then I compute the heuristic function for each and select the best. The distance between the starting point and the displacement point, as well as between the displacement point and the target, which I calculate in the usual way with the Pythagorean theorem. The problem is that in this way an object often ignores all obstacles and more often gets stuck between two positions. I understand how a dumb question might seem, but any help is appreciated.

Answer 1

Create an imaginary grid at any resolution that suits your problem: as coarse as possible for good performance, but thin enough to find (preferably) the gaps between obstacles. Your grid can also refer to the quadrant with your obstacle objects.

Run A * on the grid. The grid can even be filled with useful information, such as proximity to static obstacles. Once you have a path along the squares of the grid, construct this path into a sequence of waypoints where there is an inflection in the path. Then move along the lines between waypoints.

By the way, you do not need the actual distance (see your mention of the Pythagorean theorem): A * works great with distance estimation. Manhattan distance is a popular choice: |dx| + |dy| |dx| + |dy| . If your net game allows diagonal movement (or a fake grid), just max(|dx|, |dy|) is probably enough.

Answer 2

E. The first thing that comes to my mind is that at each point you need to calculate a gradient or vector to find out the direction of transition to the next step. Then you move a little epsilon and repeat.

This basically creates a grid for you, you can resize the cell by selecting a small epsilon. By doing this instead of using a fixed grid, you should be able to calculate even with small degrees at each step - less than 45 ° from your 8-point example.

Theoretically, you can solve formulas symbolically (eps versus 0), which can lead to an optimal solution ... just a thought.

Answer 3

How are the obstacles presented? Are they polygons? Then you can use the vertices of the polygon as nodes. If the obstacles are not represented as polygons, you can create a convex hull around them and use its vertices for navigation. EDIT: I just realized you mentioned that you need to navigate a relatively large number of obstacles. Using obstacle peaks can be unacceptable for many obstacles.

I do not know about moving obstacles, I believe that A * does not find the optimal path with moving obstacles.

You note that your object is moving backward and the fourth - A * should not do this. A * visits each point of movement only once. This can be an artifact of creating movement points on the fly or from moving obstacles.

Answer 4

I remember encountering this problem in college, but we did not use the A * search. I cannot remember the exact details of mathematics, but I can give you the basic idea. Perhaps someone else might be more detailed.

We are going to create a potential field from your playing area with which the object can follow.

• Take your playing field and tilt it or warp so that the starting point is at the highest point and the target is at the lowest point.

• Orient the potential in the goal to strengthen its purpose.

• For each obstacle, create a potential hill. For the non-point obstacles that you have, the potential field may asymptotically increase along the edges of the obstacle.

Now imagine your object as marble. If you placed it at the starting point, it should slide down the playing field, around obstacles and hit the target.

The hard part, the math I don’t remember, is the equations that represent each of these blows and wells. If you notice this, add them together to get your final field, then do some vector computation to find the gradient (just like towi said), and the direction you want to go at any stage. Hopefully this method will be fast enough so that you can recount it at every step, as your obstacles move.

Answer 5

It looks like you are implementing a Wumpus game based on a discussion of Norwig and Russell A * in Artificial Intelligence: A Modern Approach is very similar.

If so, you probably need to enable obstacle detection as part of your heuristic function (therefore, you will need sensors to alert your agent about the signs of obstacles, as shown here ).

To solve the problem back and forth, you may need to save the distance traveled so that you can find out if you have already been to the location and that the heurisitic function checks the past N number of moves (say 4) and uses that as a tie-breaker (i.e. if I can go north and east from here, and my last 4 moves were east, west, east, west, go north this time)