jerdak wrote:And yes a "bog standard" A* algorithm will work but what happens if we allow for multiple entrance portals?
Absolutely nothing. It still works.
Does it recalculate a shortest path every single time a new portal is opened?
Obviously. A new path has opened.
How does it determine if a portal on the ceiling is the fastest route?
The same way it would know any other portal. This one actually does require just a bit of intelligence behind it, only because you have to be able to tell what parts of the floor are reachable from the ceiling portal.
If I open an entrance in front of a bot and an exit over lava will it know what it's end will be.
The path going through the portal will cross lava. So yes.
That's what I mean by interesting. Searching along a 2D or Semi-2D space is easy, searching against the possibility of dropping from the sky is a bit tougher.
Not by much.
The few times I've done a path finding algorithm the search criteria had many considerations such as ammo drops, health, distance from exits, etc.
This obviously makes it more difficult, but all it does it affect the weighting of paths.
Plus with a lot of my bots I tend to pre-bake the quick routes between important areas of the map to save on later computation. Such learning would be trickier.
Actually it would be impossible. You couldn't do that anymore. Even if all the paths through portals are longer, by the time you'd be able to confirm that you'd already have *found* the shorter non-portal path, and would have stopped pathfinding.
I was perhaps not addressing what would happen but how much fun it would be to work on this problem for the next gen. game. I don't want typical, I want unique.
Pathfinding doesn't really need to be 'unique'. I'd actually prefer it not be. Intelligent, yes, but the algorithms are easy.
Edit: I am struck by something. Do you know how A* works? Well, first, it's a more efficient generalization of Dijkstra's algorithm. Basically you split the gameworld up into nodes (these usually have a bit of distance between them, but are close enough that moving between them looks fairly natural). Then, starting from your current node, you calculate the distance to all your neighbor nodes, and add the *estimated* distance from the neighbor node to the destination (this estimation must be a lower bound for A* to be guaranteed to find the optimal path). Now, drop all these distances into a priority list, and repeat the process with the lowest-distance node, until you reach the destination. Then you can trace the path backwards, and follow it.
Putting portals into the mix means two things: you need to dynamically add node-to-node connections for the nearest nodes on either side of the portal, and you need to come up with a distance estimator that takes portals into account and still remains a lower bound.
The first is trivial, and the second seems easy. A normal distance estimator is just euclidean distance - the distance if you just flew in a straight line toward them. This is obviously a lower bound. With portals, you just need to calculate several euclideans. First take the naive one, then take the euclidean from the node to a portal, and add the euclidean from the end-portal to the destination. Repeat this for every portal. Take the minimum as the distance estimation. This is guaranteed to be a lower bound, and should produce some decent results. If you're only working with one set of player-created portals at a time, this only adds four additional distance calculations (two to each portal and from each portal), which isn't horrible.