Comment by deathanatos | Hacker News Reader

Comment by deathanatos | Hacker News Reader

> Among the outline information, select the optimal point for bypassing the obstacle. (This part is the core)

Core … and a bit too vague. I'd be curious what happens to it if you run into a concave object. Image running into the back curve of a crescent, or, since diagonals are not legal moves,

       XXXXX
     XXX   X
           X
           X
 S - - >   X    E
           X
           X
     XXX   X
       XXXXX

Once you're inside such a shape, following the outline is not the optimal way around it (you'd waste time in the little alcoves at the top & bottom, and I could make those alcoves considerably more pathological, too). You'd want to head for one of the opening's corners.

Of course, the optimal path S → E avoids walking into that entirely.

Since it seems to be a game, though, the other consideration is "should the entity use optimal pathfinding?" Confounding an opponent with an odd shape could be just called "gameplay". (Different opponents might even have different levels of intelligence, and thus, different pathfinding. Some 2D games I have played have this exact mechanic.)

@deathanatos

Yes, as you mentioned, the idea of "it doesn’t have to be the optimal path" aligns perfectly with my thinking as well.

In the case of the algorithm I’m currently working on, it wouldn’t enter those concave areas directly. Instead, it would "look" at the obstacle first, recognize that the path is blocked, and then proceed toward one of the corners at the bottom or top of the concave shape. Afterward, it should be able to exit again using the same approach.

However, to make it behave more like a creature with vision in certain situations, it might be good to enhance the algorithm slightly so that it can preemptively recognize "Ah, this is a concave obstacle." That way, it could avoid inefficient behavior while still maintaining its "realistic" navigation style.

Unless the "outline" is like tensing a rubber band around the object. In that case, the collision would happen outside the convex part.

Anyway, the details are not enough for me to fully grasp the algo described.

You're referring to the "Convex Hull". And if you are inside a shape, drawing edges to the visibile vertices of the shape (until you're on the boundary of the convex hull) will easily get you a path out, and, bonus, will eventually draw a perfect shortest path to the end.

See: https://news.ycombinator.com/item?id=42608107#42626311

Imagine a maze or labyrinth, with the agent and the destination both inside of it. Is it useful to try to figure out the convex hull of the walls, even if it is effectively "the entire maze"?

The agents in the article seem to mostly be finding their way around sparsely-distributed, discrete obstacles, so I can see how the "raycasting" approach described would work well, but in a sufficiently obstructed environment like a maze, something like (double-ended) A* is going to both be simpler and likely perform better.

You can path-find using only vertices and a can-see function to generate a-star successors.

The convex hull is just where the paths will go if it has to go around an obstacle.

So if your maze is specified as obstacles take the vertices. If your maze is specified some other way it depends how expensive it is to translate it.

What you're suggesting is fine and well and good, but it will in an asymptotic analysis do more work than double ended a* that only expands successors for intersections.

Think about all the iterations where the expanded state is just one more grid cell closer to the end of the hall, vs just jumping to the end of the hall. If you limit to counting only iterations, a geometric approach is faster (vs grid).

That may not be the best way to do it in practice. It's also way harder to implement because let's face it everything is a grid.

Yeah, thank you! I couldn't find the right term.

Reply on news.ycombinator.com