Information Technology Reference
In-Depth Information
a neutral flag. They bound to a node with the minimum difference in travelling distance
(using the
Dijkstra algorithm
) from both spawn points to preserve fairness.
Collision
Points
are identified by the
degree
of the node. A high degree node most likely belongs
to a region that players are prone to meet as many different routes will lead to it. We
observed that a degree of
five
and above makes a good condition for a collision point.
Covers
are placed approximately at the meeting point of regions that have an edge to
the collision points. This helps with promoting tactical choices as it provides more op-
tions to players who are more likely to meet at collision points. Covers are also placed
at nodes which have not been assigned anything. Since these nodes are usually at region
centres, the covers act as good places to hide if a firefight is to break out at that region.
Without it, there may be too many open areas.
5.2 Evolution
Fitness Computation.
A fitness is assigned for the evolutionary algorithm to tell how
good the map is. There are 3 approaches [17].
Interactive Fitness Function
grades it
based on interaction with a player. As this is physically impossible, this approach is not
considered.
Simulation-Based Fitness Function
uses AI (Artificial Intelligence) agents
to play through a portion of the game for evaluation. Many research works ([15], [11]
and [3]) used simulation-based fitness functions. However, its weakness lies in the time
required to compute it.
Therefore, we will be employing
Direct Fitness Function
, where a content is judged
by retrieving a list of features. In our solution, the fitness is computed by simply sum-
ming up the values for all of the following features which are derived based on the
design goals presented at the beginning of this Section. 1)
Connectivity
- Returns 1 if
the graph is connected (as detected in Phase IV). Otherwise, returns 0. All regions are
reachable in a connected map. 2)
Forced Collision Points
- Returns 1 if there are one
or two collision points. Returns 0 if there are zero or more than two collision points (no
clear collision points). Ideal number of collision points depends on the map size. 3)
Flag
Fairness
- Difference in the distance travelled to own team flag. This is measured by
finding the travelling distance from the spawn points to the corresponding team flag.
The returned value is normalised to 0 to 1, with 0 being maximum distance apart and
1 being approximately the same distance apart. 4)
Overall Flag Fairness
- Similar to
Flag Fairness, but returns the difference in distance travelled to all flags from the spawn
points instead.
Evolution and Mapping.
The first population consists of three map blueprints gen-
erated with the initialisation algorithm. They are then mutated three times each, pro-
ducing nine more blueprints. Each mutation removes part of the map and repopulate
it with the initialisation algorithm. With that, the population is complete with twelve
map blueprints. Three of the best maps (based on their fitness values) are picked and
mutated three times to form the second population. This continues until enough popula-
tions are processed. The final map blueprint obtained after the evolution is then used to
create the actual environment. Doing so is a direct mapping of each abstract game tile
(in blueprint) to one of the many variations of concrete and matching game tiles seen
by the player.
