Artificial intelligence is a
scientific term that gives nonhuman entities algorithmic and mathematical
solutions for problem solving and simulating human thought and decision making.
In films, this is often depicted as a mechanical robot trying to act human. In
computer or videogames, it is the heart and soul of the nonplayer characters
(NPCs) controlling our enemies and allies.
Typically, we think of games such as
chess, checkers, and backgammon as intellectual and sophisticated games,
therefore a machine that can simulate being an adversary (especially a
masterful one) has been a way for researchers to validate their AI techniques.
Since computers can process mathematical instructions and perform iterations
(repetitive processes) very fast, researchers in AI use these skills to
simulate human thought.
As game designers, we must not only
plan our vision but try to conceptualize each idea and how it can be expressed
through a mathematical expression or logically arrived at through a database
search or script. You will discover that simple, everyday activities are in
fact very complicated and complex concepts.
Pathfinding is probably the single most popular and
frustrating game AI problem in the industry. Games like role-playing games (RPGs)
and real-time strategy games (RTS) often have characters sent on missions from
their current location to a predetermined, player determined, or menu-selected
waypoint (destination). The perfect situation of a movement would be a
no-collision or obstacle path.
The typical path from a character’s current position to the destination (waypoint) usually passes directly through one or more obstacles.
The first solution in avoiding these obstacles is to
“ride the rail” or walk around the object’s surface until you’re free to
continue toward the destination.
Although the “riding the rail” algorithm solves the
problem of avoiding obstacles, it looks silly and unrealistic, sort of a blind
person’s path solution.
The next solution is to make the path less blocky by
connecting points of the hypotenuse of the triangles.
The last issue to make the path to our waypoint truly
realistic is to curve the path.
The way to simulate a realistic character movement in
3D is to plot a straightforward path from the character’s current position to
its destination and record all of the obstacles from a world table that lie on
this straight line. For each obstacle, calculate the original collision point
and the two tangent points on either side of the obstacle. The point closest in
distance is the one selected to be connected as the hypotenuse of the triangle.
There are several techniques to achieve this
pathfinding problem, such as algorithmic (equations) or methods such as “flood
fill” and “A*” (pronounced “A star”) solutions. A flood fill is similar to a
graphics application’s “paint” tool, which will completely color a given area.
If we were to flood fill the white area with black, it
would continue filling until it hit a non-white spot.
If we were to start on location “A,” the fill would
traverse in all directions until the new space was non-white.
Each space or “node” would check its neighbors in the
four directions, and if the neighbor is white, it would be changed to black.
This recursive (repeating) process would repeat until all four directions
starting with node “A” return a “false” or no non-white connecting nodes are
left.
The A* algorithm is similar. A node is placed on an
“open” list, and if a shorter node path is found, the new path replaces the
current path (which gets placed on a “closed” list). The shortest path from a
start node to a destination node is the final path left when all paths have
been searched.
The objects that are on the map as collision areas
should include the static objects like buildings, water, fences, and so on, as
well as dynamic, moveable objects like vehicles, people, and floating bridges.
The game design may include the ability to destroy objects like buildings and
bridges, thereby modifying the original list of static objects. Another game
design might require that characters avoid areas due to hazardous conditions
that may be in effect under certain conditions or for a certain time period or
avoid specific tribes and clans. These avoidance issues greatly change the
terrain path created. One solution would be to dynamically (on the fly) set
these areas when needed as an obstacle block or zone and let the path-finding
function handle this as though it were a large building to walk around.
The solutions discussed thus far don’t take into
account various terrain elevations. Nature has rivers running downhill, and our
characters would probably prefer a downhill path to town rather than a Mount
Everest climbing shortcut. The distance over Everest may be the shortest, but
its elevation and treachery makes it less desirable. If each node had an
elevation factor, the path created would be the shortest path within reason.
Otherwise, the character’s morale and fatigue factors would be greatly
increased, causing negative results later. The elevation factor could also be
used in the character’s “line of sight” functionality. If a character were
standing in a ditch, that character probably wouldn’t see the massive horde of
enemy troops heading toward him in the distance. On the other hand, a fort on
top of a mountain would have its residents’ “line of sight” able to see quite a
distance and its cannons able to fire a long distance. If a character is
standing on one side of a building, the enemy approaching from the other side
would be unnoticed since the character’s “line of sight” would be blocked by
the building. These factors add to the realism of the game, and that’s what
players demand. That’s what your game design should include.
Other pathfinding issues would include formations
(groups of moving objects) and the turn radius and ramping up or down speed to
initialize a movement and terminate a movement. A formation is a group of
characters all moving independently but as a group. Soldiers in two columns
march behind their leader. As the leader turns, so does the entire troop. They
all must maintain their relative distance from the row in front of them, march
at the same speed (pace), and turn their bodies relative to their path line.
The leader may be marching north as the last soldier in the line is still
marching east 50 feet behind the leader. Formations also must not collide and
bounce off each other like billiard balls. These are complex structures that
must be in your game design and algorithmically understood by the team
developing your vision.
Humans are bipeds and, if they are moving the wrong
direction, can turn on a dime and reverse their movement toward the goal.
Vehicles and horses need more space to create a turn radius. Your car needs to
circle or turn around when reversing from the road south to the road north. We
have fancy terms like the “U-turn” and the “K-turn” when a car is reversing its
direction. People can perform this maneuver with an “about face” motion. These
factors must be incorporated into the game design for a realistic look and feel
in your game. People, horses, and vehicles don’t jump into a quick speed and
just stop on a dime at will. Moving objects need to increase their speed
(velocity) and decrease it before coming to a complete stop. These factors are
not easy to implement but should be addressed in the design document and
discussed as the game is being developed. Often, ideas, concepts, and features
that are in the design document hit the cutting room floor (do not make it to
the final product). These design document items should be frequently discussed
and addressed to determine their status as to whether they are “in,” “out,” or
“on hold” for the final product. Most items, given enough development time and
money, can be implemented. In reality, developers don’t have this luxury of
unlimited time and available finances.
AI is an important consideration in the success of
your game. Often, I read on Internet gaming sites that the development team
planned to do AI last and within a week or two. This inexperienced and ignorant
decision severely delayed the project, and the AI was quickly finished without
a real solid solution. The teams have often said in the aftermath of a major
project that they wished they had started the AI earlier and had longer to work
on the best AI possible (not the best AI as soon as possible).
Tidak ada komentar:
Posting Komentar