Skip to main content
gamedev.net
🔒 Locked

Pathfinding through interest points

Started by DrEvil 2 replies 1.6k views
Original Post
DrEvil
DrEvil
Soon I will be modifying my path planner for my bot in order to support the ability to pathfind through places of interest on the way to the goal. As an example, in a deathmatch game during the bots normal navigating to higher level goals, like weapons or players they are hunting, I want the path to favor going through health and armor if the bot needs it. I presume that during expansion of each node along the graph, if it's a node of interest(health or armor), I can use this knowledge to bias to this path by a modification of the cost calculation. My question is, what is a good metric for modifying favorable paths like this? Should I multiply the given cost of the path up to that point by .75 or something, or would better results be achieved by a more specific modification to the final cost or the heuristic cost? Any ideas how I can achieve the desired results?
LorenzoGatti
LorenzoGatti
Assuming there is a graph to run A* on and that places of interest correspond to subgraphs (including individual nodes), each edge can have a true movement cost and a figurative cost used for path planning.
Starting from the true costs I would drastically decrease, up to 0, the figurative cost of edges entering and leaving the regions of interest, but not those within them.
This way plain A*, without thrilling hacks, would prefer some detours through regions of interest to shorter useless paths, there would be no risk of zero-cost loops inside the regions of interest, and paths that end inside regions of interest shouldn't be particularly biased (each possible entry into the region has a similar discount).
Omae Wa Mou Shindeiru
TechnoGoth
TechnoGoth
One method I saw once, was running A* against an influence map. Everything has a base cost of 1. But the cost is altered based on the value of that space. If the bot is low on health then the cost of going through a health node drops proportionally. Likewise areas that are known to be dangerous have an increased cost.
BrianL
BrianL
Influence maps sound reasonable for increasing opportunity (ie picking a path that gets close to valuable locations), but I don't know if you want to use it to actually pick them up. For example, if you have two equally good paths, but one goes close to the red armor, the AI should generally prefer that path.

Picking up up sounds like something better handled by making that location a specific goal. This would allow delaying decision making (ie don't plan too far ahead as the world state may change rapidly). This also gives tighter control over when the AI goes, which they go to, etc.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.