Public Group

# Movement range algorithm?

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

## Recommended Posts

Ok, so as pictured here: http://www.flickr.com/photos/27840310@N04/ I am creating a hex map turn based strategy game. Things are actually moving along pretty well right now but I've hit a snag while trying to implement the standard mobility point based movement system. Now, going into it, I really thought that the pathfinding would be the hardest part in terms of finding the optimum path between the starting point and destination. Well I studied up on a* and got that part working fine. My problem now, that I can't really figure a good way to solve, is that I want to be able to display a given characters movement range upon clicking on it (ie highlight all tiles it can move to this turn). Now, in my own attempts I do have a method that "works" in terms of it gives the desired results even if it is INSANELY slow (and I knew it would be when I coded it, I just didn't know how slow). That solution is to basically recurse through all possible paths in every direction and is incredibly inefficient and redundant. My current thinking is that I'll need to set up a vector to store the tiles that can be reached so as to prevent them from being checked again. But then I'm not quite sure how I would deal with having to move around obstacles because then the order in which I check tiles would come into play. My other thought was to approach it from the opposite direction. As step one, I could fill the aforementioned vector with the "maximum" movement area. That is, take the characters movement points and assume every tile, regardless of terrain, takes 1 point. Then I could take this somewhat limited vector and test every tile with a (perhaps slightly modified) a* algorithm. This still seems inefficient, but not as bad as some other methods maybe? Any thoughts? However, my other thought was that

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 11
• 9
• 9
• 43
• ### Forum Statistics

• Total Topics
634131
• Total Posts
3015719
×