· 8 years ago · Feb 18, 2018, 06:02 PM
1Week 1
2
3AI: The process or science of creating intelligent machines
4
5Types of AI
6 - Deterministic AI
7 - Predictable, Pre-specified
8 - fast
9 - easy to implement, understand, test and debug
10 - literally just if this, do that
11 - DOES NOT LEARN
12 - Non Deterministic AI
13 - unpredictable, degree of uncertainty
14 - developers don't code explicit scenarios
15 - emergent behaviour
16 - character learns to adapt to situations, and makes decisions based on experience
17 - difficult to test and debug
18
19Agents
20 - AI Entities
21 - have Sensors - ie/ eyes
22 - have effectors - ie/ hands
23
24Performance Measure
25 - Agents need a way to determine if a decision gets the most bang for its buck.
26 - in short, must have a way to determine success
27
28Types of Agents
29 - Rational Agents
30 - tries to do right thing based on rationale
31 - does what is expected to maximize performance measure
32 - Reflex Agents
33 - Cause and effect
34 - IF going to hit shit, THEN brake
35 - Goal Based Agents
36 - bases decisions of what the end result should be
37 - Utility Based Agents
38
39Problem Solving Techniques
40 - Single State Problems
41 - 1 cause produces effect
42 - Multiple state problems
43 - Contingency Problems
44 - dealing with potential issues before producing the effect
45 - Interleaving
46 - dealing with potential issues while producing the effect
47 - Exploration
48 - let the AI figure it out
49
50Search Strategies
51 - in discovering a earch strategy, look for
52 - Completeness - will this find a solution?
53 - Time Complexity
54 - Space complexity (how much memory)
55 - Is it optimal?
56 - Breadth First Search - LOOK UP
57 - Depth First Search - LOOK UP
58 - Uniform Cost Search
59 - Hill Climbing
60
61AI Game Engine Components
62 - Game Engine Components Diagram in Week 1
63 - just re read it.
64
65AI Engine Concerns
66 - Decision making
67 - how reactive are agents
68 - how realistic are their actions?
69 - Input
70 - is it boolean (ie: I SEE YOU) or value based (ie: He' 10 m away);
71 - how often is each agent updated?
72 - how quick do they react?
73 - Will the engine check agents regularly? or will agents trigger engine events?
74 - Navigation
75 - how will things move?
76
77Week 2
78
79Movement algorithms take world input and move things
80
81Kinematics - each character has a position and orientation, velocity and angular velocity
82
83SEEK CODE
84
85 steering.velocity = target.position – character.position;
86
87FLEE CODE
88
89 steering.velocity = character.position - target.position;
90
91WANDERING CODE
92
93 steering.rotation = randomNumber() * maxRotation;
94
95CHASE / EVADE
96
97if(predatorX > preyX)
98 predatorX--;
99else if(predatorX < preyX)
100 predatorX++;
101if(predatorY > preyY)
102 predatorY--;
103else if(predatorY < preyY)
104 predatorY++;
105
106
107Week 3
108
109Pathfinding
110 - METHOD 1 : map to closest point on path, target is selected further along
111 - METHOD 2 : predict where char will be, if too far from path, adjust steering
112
113if(posX > destX)
114posX--;
115else if(posX < destX)
116posX++;
117
118
119 - Waypoint
120 - uses a path table, which establishes connections between nodes
121 - Breadcrumb
122 - other thingy drops bread crumbs
123
124Separation
125 - use 270 degree cone to detect.
126 - characters don't need to separate from something behind them
127 - Linear separation
128 Strength = maxAccelleration * (threshold – distance) / threshold;
129
130 - Inverse Square separation
131
132Strength = min(k / (distance * distance), maxAccelleration)
133
134
135Collision Avoidance
136 - Cast a ray ahead of the character, if a collision is imminent, adjust for it well before it occurs
137
138
139Week 4
140
141Combined steering algorithms may need to
142 - keep the character safe
143 - avoid walls
144 - reach intermediate points before goal
145
146Weighted Steering
147 - multiple steering algorithms, with different amounts of influence on course.
148
149Steering doSteering(){
150 steering = new Steering();
151 steering += behavior.weight * behavior.behavior.getSteering();
152 steering.linear = max(steering.linear, maxAcceleration)
153 steering.angular = max(steering.angular, maxRotation)
154 return
155
156Classic Flocking
157 - Three rules for flocking:
158 - Cohesion – Have each unit steer towards the average position of its neighbours.
159 - each member steers towards the average heading
160 - each one moves in relation to the average position.
161 - Alignment – Have each unit steer so as to align itself to the average heading of its neighbours.
162 - Separation – Have each unit steer to avoid hitting its neighbours
163
164Steering pipeline
165 - targeter - figure out goal
166 - decomposer - break goal into sub goals
167 - constraint - limit ways to achieve this goal
168 - actuator - limit how character can move
169
170Week 5
171
172Coordinated Movement
173 - two appraoches to moving groups of characters:
174 - have each boid make its own decisions, or
175 - designate a leader to make decisions and have all other boids follow; this is called formation motion
176 - formation motion is the movement of characters such that they retain group organization; types:
177 - fixed formations (e.g. party formations in Icewind Dale)
178 - simplest to implement; uses fixed geometric formations
179 - each position is considered a "slot"
180 - formation is oriented such that the leader is located in the leader slot and additional characters fill the other slots
181 - requires no kinematics or steering
182 - useful for small groups; difficult to control otherwise
183 - scalable formations
184 - fixed formations that can be modified to add or decrease boids as needed
185 - implemented by not specifying the number of slots until needed
186
187 - emergent formations
188 - different approach to scalability; gives each character steering control
189 - boids are expected to construct a fromation based on location of other boids
190 - group has no leader
191 - advantage: allows characters to react individually to different situations/obstacles
192
193
194 - Two-level formation steering
195 - combines fixed formation with emergent behaviour
196 - allows for situations where the leader approaches an obstacle and needs to avoid it
197 -rather than leader and followers avoiding the obstacle:
198 - create an 'invisible' leader
199 - have real leader execute avoidance behaviour
200 - invisible leader and followers continue as normal
201 - transfer control back to real leader
202 - can be extended further to create formations of formations
203 - formation slots assigned based on slot weights and can be assigned manually or by using an algorithm
204
205 - Moderating formations
206 - because boids may have to avoid obstacles, they may get out of sync with others; to prevent this, make the max speed of the formation equal half that of the characters themselves
207
208- Motor Control
209 - focus is on movement based on physics; prevalent in racing games
210 - requires special constraints:
211 - output filtering
212 - simplest to implement; involves removing all unnecessary steering options (e.g. sheep fleeing if dog is not close)
213 - downside is that unnecessary behaviours may have been contributing to realism of character
214 - capability-sensitive steering (e.g. maximum speeds, etc.)
215 - takes character's abilities into account
216 - movement and steering are combined to create more realistic behaviours
217 - common actuation properties
218 - I have no idea what this actually means
219 - vehicles have limited capabilities with arcs representing their range of motion
220 - following recommended heuristic:
221 - accelerate if stationary
222 - if moving and target lies between 2 arcs, turning at max rate will not cause skid
223 - if target is inside forward arc then continue steering towards it; if target is inside rear arc, accelerate backwards and steer towards it
224 - special constraints of a car include:
225 - can't turn while stationary
226 - turning speed decreases with velocity
227
228
229Week 6
230
231Pathfinding graphs
232 - diagram used to repesent a path or series of paths
233 - circles are nodes
234 - lines are connections
235 - a path consists of one or more connections
236
237
238
239
240Weighted graphs
241 - each path ia assigned a cost value
242 - this cost can be in the form of either time or distance
243 - if character is standing at the goal node, the cost would be zero; the further the character is from the goal, the higher the cost
244 - total path cost is the sum of the costs of each connection in the path
245 - there are no negative costs
246
247
248Directed weighted graphs
249 - adds direction to connections to prevent characters from backtracking
250
251A* pathfinding
252 - algorithm to find path with minimal cost
253 - iterates through the entire graph of nodes
254 - at each node, all outgoing (connected) nodes are considered
255 - there is selection criteria for choosing next node
256 - each current node keeps track of:
257 - cost so far
258 - distance from goal
259 - previous node
260
261 - node types:
262 - open nodes are ones that have not been processed (ones that have not yet been used as the current node)
263 - closed nodes are ones that have been processed (ones that have already been used as the current node at some point)
264 - algorithm is repeated until distance from the goal is zero (the current node == the goal)
265 - all paths are calculated but only the best path is stored
266 - heuristic = cost - cost so far
267 - estimated total cost = cost + heuristic
268
269World Representation
270 - pathfinding is done with nodes and connections, but most games are not made of such things; therefore need a way to translate path into the world representation
271 - quantization: converting a character's movement into a spot on the tile graph
272 - localization: opposite of quantization; to take a character's tile-based location and convert it into world location
273 - validity: if a path indicates a movement from A to B, then the world should make it possible for the character to move there
274
275Tile graphs
276 - the 2D tile system still exists within the code of the game, albeit not graphically
277 - still used extensively in RTS games
278 - used to split world into square regions
279 - regions are generated outside of AI
280
281Dirichlet Domains
282 - used to generate points around the world with an area around each point
283 - can be used instead of tiles
284
285
286
287 - tile-based approach is blocky, wherease dirichlet is smoother/more realistic: