Jump to content
  • Advertisement
Sign in to follow this  

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

This topic is 2266 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,
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
Thanks
Jack

Share this post


Link to post
Share on other sites
Advertisement
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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!