Jump to content
  • Advertisement
Sign in to follow this  

WHCA* requires precomputed costs, it may be difficult to achieve

This topic is 2775 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

One of the requirements of WHCA* is precomputed costs of every combination of source and destination on start-up of the program. Consider I have a map of 300x300 tiles big, it would require quite a lot of time to complete during start-up. Do I give up on WHCA* and search for a cheaper solution or there is a workaround for precomputed costs?
I have considered using real-time search, but the amount of traffic is huge. that may not be a feasible solution as well

Share this post

Link to post
Share on other sites
Hi Jack,

I suggest that you create an algorithm for placing nodes.
Even if your 300x300 map is a tightly packed labyrinth, I think it's likely less than a quarter of the passable tiles will have nodes on them. Make the node placing algorithm search for portals between sectors and place one node in each side of the passageways. Also, add nodes to corners.

A naive improvement to this technique is to place uniformly distributed nodes randomly across the passable terrain, allowing agents to 'dodge' stuff by routing their path through them. I noticed that you're having issues with agents passing one another: If no nodes are nearby, you may be able to add a circumvention node to a local section of the tree, although that might be difficult (haven't tried it yet)

Obviously, you can also create special nodes that are of an inherited type to mark ideal vantage or cover points as well as vending machine interaction spots etc.

But please don't create a node for each tile. That's a classic thing people start doing when first using A* for tiled maps.
It looks like you know your stuff well, aside from that. -Take no offense! smile.png

Good luck with your project!

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!