- 1 Under construction
- 2 Types of navigation data
- 3 World layout
- 4 2-D vs 3-D
- 5 Real-time Mapping
- 6 Alternate costs
- 7 Finding valid paths
- 8 Movement systems (following paths)
- 9 See Also
This article is kind of a stub, I'm working on filling it in. There's some bullet points for an overview of what will be described. The information here will NOT be application (e.g. game) specific, but may use examples based on a particular game.
Also known as a series of waypoints, this type of data defines a fixed path, rather than a dynamic navigation set. In terms of LavishNav, a path is defined as a series of connected regions. LavishNav provides the lnavpath LavishScript object type for this type of system, and are usually dynamically generated by selecting the shortest path from region A to region B. This does, however, represent the simplest form of navigation, and can of course be stored in LavishNav.
- Representing a linear path
- Start region
- Additional regions
- Finish region
For a linear path to work, each region must be connected from start to finish. A pure linear path is uni-directional, but may of course be bi-directional.
A road can be considered a linear path, at least when it contains no forks. If the road contains a fork, multiple linear paths (consisting of the original road and the additional road or roads) are connected as a whole to form a mesh.
Fixed grids are meshes with given restrictions on movement and region size, and perfectly aligned. 2D grids generally have 4 (cardinal) or 8 (with diagonal) directions of movement, and are commonly used for map layouts in video games, especially scrollers -- move one screen up, two screens right, and so on. 3D grids extend the 2D grid to include up and down, and thusly could have 6 or 18 directions of movement.
Fixed grids can be represented by sets of rectangles (2D grid) or boxes (3D grid), generally of fixed size (or increments of a fixed size). Each region is then connected to any adjacent region that can be moved to from that region.
A free-form mesh is similar to the fixed grids explained above, but with no restrictions on alignment, size, adjacency or direction of movement. Any region may directly connect to another region that can be directly travelled to, even if the path followed by the connection crosses through other arbitrary regions. It is wise, of course, not to connect to regions too far away.
Note: This section deals specifically with world navigational systems, which are for general navigation across a world, rather than locale-independent navigation, such as hunting areas.
A universe, by definition, contains everything. Fortunately, a universe is a logical, rather than physical, construct. This is another topic, but our effective universe in reality, which we cannot physically leave may conceivably be one of many other effective universes, but that's useless to know if we can never see or move outside of it, so our logical universe is perfectly suitable for all intents and purposes. In games, we can travel between logical universes, and we have the added benefit of knowing which universe we (or any arbitrary point) are actually in. Additionally, wherever the game clearly indicates exactly what is containing a given location, a logical universe exists and can be defined -- for example, a "zone", "sub-zone", etc -- regardless of the type of border (e.g. continuous movement or a loading screen).
- EverQuest has planets (or a planet, moon, planes, etc, but that's not the real point), continents, and zones
- Greater Faydark
- Lesser Faydark
- World of Warcraft has planets, continents, zones (continuous movement as well as loading screens for instances, etc), and subzones
- Eastern Kingdoms
- Elwynn Forest
- Fargodeep Mine
- Trade District
- Mage Quarter
- Elwynn Forest
- Eastern Kingdoms
For EverQuest zones, the reason for using a universe is fairly obvious. Most EQ players know that each zone is basically its own little world, and it is completely separated from all other zones, including each having its own separate coordinate system (see the Overlapping coordinate systems section of this article for local-level travel between overlapping coordinate systems). But for WoW, things are less obvious. Entire continents define the coordinate systems, and zone borders are intermingled or jagged. This brings up some interesting problems because universes have no discernable borders, but zones do. In WoW, specifically, there is also no easy way to determine if a given point is in a given zone, as zones are not defined by a single rectangle. The easiest way to handle this is to duplicate the regions along the real borders such that they are in both universes.
Overlapping coordinate systems
2-D vs 3-D
- Recording movement
- Data density
- Translating collision data into navigation data
- Dealing with false positives and false negatives
- Uni-directional vs bi-directional
- Time versus distance
- Tolls, level/item/etc restrictions
Finding valid paths
- Point to point
- Point to many
- Avoiding dynamic objects
- Travelling salesman (shortest path, requiring a set of points be visited)
Movement systems (following paths)
- Real-time validation of navigation data
- Getting un-stuck
- Movement axes