Jump to content
  • Advertisement
Sign in to follow this  
moeen k

How To Update List Of Passed States In A*

This topic is 719 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi.

my questions is short. in a game with moving goal like player that moves around, how list of states that shows our agent has passed these states? for example when player has changed position, maybe our agant needs to go to those states or positions again, how and in which conditions should we update those states?

 

thank you for helping

Share this post


Link to post
Share on other sites
Advertisement
A* as an algorithm doesn't deal with changing circumstances, or care about what you do with the results it gives you. It finds a list of states to reach a goal, and how you handle that is up to you.

Typically, you want A* to give you that list of states, and then A* is out of the equation. You just need a system for working through the states. A typical method for pathfinding is for A* to return a list of positions, and then for some steering code to steer the player towards the first position. Once the player is at that position (or close enough), we just move on to the next. When we run out of positions, we're at the destination. Edited by Kylotan

Share this post


Link to post
Share on other sites

Not sure what "state" means with A*. If you need intermediate positions on the optimal path, then you can use the nodes on the optimal path from the closed list.

 

The closed list contains all positions that were computed, with their distance from the start and the heuristic value. They also contain downstream pointers to their predecessor node towards the the starting point. Some of the nodes on the closed list are on the optimal path, some others are not.

 

After reaching the target node in A*, the algorithm terminates, and you use the downstream pointers to walk back towards the starting point, to find out in which direction to go.

During that walk, you visit all nodes on the optimal path.

 

After doing one step on the optimal path (from the starting node), you're still on the optimal path, so you can use the same downstream pointer walk again, to find the direction to go with the second step, and so on.

 

Obviously, this is not very optimal. It's better than doing a new search every step of the way, but you're still walking all remaining nodes on the path you still have to go, to decide the direction of one step. Simpler options are

1) After finishing A*, do a downstream walk, and reverse the pointer direction from downstream to upstream (ie point into the direction of the target). Then you can simply get a node from the closed list, and the upstream pointer immediately points in the direction to go.

2) Essentially, your nodes with upstream pointers form a list of nodes to visit. Rather than storing this in the closed list, you can also make a new list of nodes to follow, and attach that to whatever must follow the computed path. It just pulls the next (upstream) node from the list, and immediately knows where to go, just like 1. However, since you make a copy, you can omit irrelevant information, such as the cost, the heuristic value, and all nodes not on the optimal path, freeing some memory.

Share this post


Link to post
Share on other sites

Not sure what "state" means with A*.


A* is a state space search. In games, when used for pathfinding, each of those states is usually a geographical location - but the base algorithm doesn't need to know or care about that. Edited by Kylotan

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!