LavishNav:Implementation Considerations
Contents
Under construction
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.
Linear paths
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
- universe
- 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
Fixed grids are meshes with given restrictions on movement and region size. 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) of fixed size. Each region is then connected to any adjacent region that can be moved to from that region.
Free-form meshes
A free-form mesh is similar to the fixed grids explained above, but with no restrictions on adjacency and 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.
World layout
- Translating world layout into LavishNav universes
- Overlapping coordinate systems
- Layered navigation
2-D vs 3-D
Real-time Mapping
- Recording movement
- Data density
- Translating collision data into navigation data
- Dealing with false positives and false negatives
- Uni-directional vs bi-directional
Alternate costs
- 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
