|
 Features
Storing
it Better
Even
if the A* search is relatively efficient by itself, it can be slowed down
by inefficient algorithms handling the data structures. Regarding the
search, two major data structures are involved.
The first is the representation of the playing area. Many questions have
to be addressed. How will the playing field be represented? Will the areas
accessible from each spot-and the costs of moving there-be represented
directly in the map or in a separate structure, or calculated when needed?
How will features in the area be represented? Are they directly in the
map, or separate structures? How can the search algorithm access necessary
information quickly? There are too many variables concerning the type
of game and the hardware and software environment to give much detail
about these questions here.
The second major structure involved is the node or state of the search,
and this can be dealt with more explicitly. At the lower level is the
search state structure. Fields a developer might wish to include in it
are:
The
location (coordinates) of the map position being considered at this
state of the search.
Other
relevant attributes of the entity, such as orientation and velocity.
The
cost of the best path from the source to this location.
The
length of the path up to this position.
The
estimate of the cost to the goal (or closest goal) from this location.
The
score of this state, used to pick the next state to pop off Open.
A limit
for the length of the search path, or its cost, or both, if applicable.
A reference
(pointer or index) to the parent of this node-that is, the node that
led to this one.
Additional
references to other nodes, as needed by the data structure used for
storing the Open and Closed lists; for example, "next" and maybe "previous"
pointers for linked lists, "right," "left," and "parent" pointers
for binary trees.
Another issue
to consider is when to allocate the memory for these structures; the answer
depends on the demands and constraints of the game, hardware, and operating
system.
On the higher level are the aggregate data structures-the Open and Closed
lists. Although keeping them as separate structures is typical, it is possible
to keep them in the same structure, with a flag in the node to show if it
is open or not. The sorts of operations that need to be done in the Closed
list are:
Insert
a new node.
Remove
an arbitrary node.
Search
for a node having certain attributes (location, speed, direction).
Clear
the list at the end of the search.
The Open list
does all these, and in addition will:
- Pop the
node with the best score.
- Change
the score of a node.
The Open list
can be thought of as a priority queue, where the next item popped off is
the one with the highest priority-in our case, the best score. Given the
operations listed, there are several possible representations to consider:
a linear, unordered array; an unordered linked list; a sorted array; a sorted
linked list; a heap (the structure used in a heap sort); a balanced binary
search tree.
There are several types of binary search trees: 2-3-4 trees, red-black trees,
height-balanced trees (AVL trees), and weight-balanced trees.
Heaps and balanced search trees have the advantage of logarithmic times
for insertion, deletion, and search; however, if the number of nodes is
rarely large, they may not be worth the overhead they require.
Fine-Tuning Your Search
Engine
|
|
|
|
|
