0
\$\begingroup\$

I'm working on a grid based game/prototype with a continuous open map, and are currently considering what size to make each segment. I've seen some articles mention different sizes, but most of them is really old, so I'm unsure how well they map to the various platforms and performance demands common today.

As for the project, it's a hybrid of 2D and 3D, but for path-finding purposes, the majority of searches would be approximately 2D. From a graphics perspective, the minimum segment size would be 64x64 in the XZ plane to minimize loaded segments while ensuring full screen coverage. I figure pathfinding would be an important indicator of maximum practical size.

Addendum:

I realize I was a bit unclear when talking about sizes and segments.

Each segment is a cubical map of blocks, e.g. 64x64x64 blocks. These represent both geometry, but also if an actor can move into that location and is thus a potential node in the graph.

Each of these segments again combine to a larger square or cubical world map. Neighboring segments are to be loaded dynamically to ensure a seamless local map.

Therefore how many blocks fit into the screen space when rendered, sets a practical minimum for the segments, but we would probably want to have larger segments than the absolute minimum. However, since a block also represents a potential node, the segment size also affects the size of the graph, which have to be considered when choosing a segment size.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ Isn't that something you could just set in one place in code and then change it later when the system is built to see the real-world ramifications of certain values? \$\endgroup\$ – Tetrad Nov 21 '11 at 8:47
  • 1
    \$\begingroup\$ When you say "64x64", what sort of units are you talking about? Is that pixels? What resolution is the screen? Is that the size of your tiles, or is that the size of something else? I'm not really sure what you mean by "segment" or "segment size". Can you elaborate a little? \$\endgroup\$ – Trevor Powell Nov 21 '11 at 9:23
  • \$\begingroup\$ In this case it's "blocks", roughly translatable to 1 meter or yard. When rendered, it will probably be 16 or 24 pixels in width. \$\endgroup\$ – Jo-Herman Haugholt Nov 21 '11 at 11:59
  • \$\begingroup\$ By segments I mean what I guess is often called world offsets. Each segment represents local space, and probably four segments will be loaded at a time to enable a seamless map. \$\endgroup\$ – Jo-Herman Haugholt Nov 21 '11 at 12:03
  • \$\begingroup\$ The blocks also form the grid in which actors move. \$\endgroup\$ – Jo-Herman Haugholt Nov 21 '11 at 12:06
3
\$\begingroup\$

Individual units are completely arbitrary and meaningless to the outside world. What matters is the topology of your search space. You need each segment to be small enough to ensure you can reach all the areas of the map that you want to be able to reach, but as big as possible in order to complete the searches more quickly.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ But what is a typically good size for the graph of the search space? Or rather, what is typically to big? \$\endgroup\$ – Jo-Herman Haugholt Nov 21 '11 at 13:47
  • 2
    \$\begingroup\$ You keep using this word size and its very confusing. The two main performance issues you are going to have is memory which is limits the total number of nodes and edges and density which impacts the performance of the actual search. You sound like you are using size to refer to distance between nodes which has no performance implications. \$\endgroup\$ – ClassicThunder Nov 21 '11 at 14:29
  • 2
    \$\begingroup\$ There is no 'typically'. It depends on how much time you have available for the search, how much memory you have available, how good your heuristic is, what the average branching factor of your graph is, how well optimised your implementation is, what platform you're running on, and so on. \$\endgroup\$ – Kylotan Nov 21 '11 at 14:34
  • \$\begingroup\$ @ClassicThunder Yeah, I see how I was unclear. I'll append the question. \$\endgroup\$ – Jo-Herman Haugholt Nov 25 '11 at 14:21
  • 1
    \$\begingroup\$ No. It's entirely dependent on your search space and your application requirements. Your amendment to your question doesn't help because it just emphasises that you have 2 grid granularities - why search through the large one (or worry about its size) when the small one is the only thing relevant to characters? Most people using A* don't have these 2 tiers, so even if there could be a standard, it wouldn't apply to your question. \$\endgroup\$ – Kylotan Nov 25 '11 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.