Jump to content
  • Advertisement
Sign in to follow this  

What's a good cell size for HPA to cover a whole continent

Recommended Posts

if you have 40x40 cells in the map, and there will be 10x10 cells per cluster then there are 4 clusters per side and 4x4 = 16 clusters in total

if one cell is 10 meters
the max. extent is 400x400 meters

so the bigger cell size the bigger the extents, also dependent on maximum cells allowed

if the size of North America is 24.71 million km² (or 2.471 × 10 pow(13) m square), how would you choose a good cell size for it and you have probably a limited number of cells allowed because of the calculation time complexity?


Share this post

Link to post
Share on other sites

I don't know of any game that does that, for several reasons.


First off, games don't actually cover that much area.  Game worlds are substantially smaller than the world around us.  WoW is around 60 square miles of actual content. Dragon Age 3 and Skyrim were both about 20 square miles of content.  I'm not aware of other mainstream games that have more actual content. GTA5 is the still the biggest mainstream game area with about 100 miles (so in the 5000-8000 square mile range) yet mostly cookie-cutter buildings plus vacant areas. The actual modeled content covered under roughly 10 square miles divided into many small zones.

Enormous worlds are difficult to fill with interesting content. If you are thinking about multiplayer games, population is also an issue. If you've got 27 million square kilometers and want people to interact with each other you'll need to cluster them together tightly and still be mostly vacant. Even if you had 27 million players spread evenly that means one person per square kilometer. Being a kilometer away from your nearest neighbor doesn't lend itself to interactions, an 27 million players is hard to come by. For reference, WoW hit 12 million active subscribers at its peak.


Even if you decide to build up a giant world like those games, you still are unlikely to need a system like HPA* (Hierarchical Pathfinding A*).  In the large games they build out by zone, and have each zone connect smoothly with each other. Generally the games are built so pathfinding of in-game objects stays within a small area within a zone. Players can travel between zones, but usually only through designated areas. Those areas follow a hierarchical system, but there are normally very few transition points so the connectivity graph between zones is extremely simple. 

Instead of a more complex HPA* system, the games typically use A* within the zone, and for inter-zone travel use a pathfinder on a larger (one, not hierarchical) graph that is carefully built by designers. The map designers designate a single point for each zone transition.  So the inter-zone pathfinding might say to travel to zone 4, zone 19, zone 43, zone 76. The player would use a lookup table to find the transition point between zone 4 and zone 19 and route to it.  Then after traveling there, they'd find the transition point from zone 19 to zone 43 and route to it.  Repeat for the transition point from 43 to 76, and finally from that point to the final destination.


And if you're looking for purposes other than games, I imagine there are better systems like those used by navigation programs. But they also probably rely on hand-edited transition points by the people who build the maps.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
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!