Artificial Intelligence – Steering Behaviours for Autonomous Agents (personal notes) May 31, 2007
Posted by deltawing in Uncategorized.add a comment
- SEEK: desiredDirection = norm(targetPosition – currentPosition)
- FLEE: desiredDirection = norm(currentPosition – targetPosition)
- PURSUE:
- EVADE:
- COLLISION DETECTION (Zero Overlapp): Each Mover checks its distance against other Movers in the world to see if it has collided. If so, get the amount overlapped, and move that distance in the opposite direction away from each other.
Kinematic Steering
Simple implementation of steering behaviours. Movers can suddenly change their direction of movement. This is not realistic but works.
Dynamic Steering
Takes into account Newton’s law that a moving object cannot suddenly change in velocity (linear or angular). This models real-life behaviour.
The A* Pathfinding Algorithm Personal Notes and Pseudocode May 31, 2007
Posted by deltawing in Computer Science, Programming.add a comment
These are personal notes. If they don’t make sense to you, that’s because they probably shouldn’t. 🙂 If you can make sense of it, you are a genious!!
Graph
A graph has nodes and connections.
Nodes (pn: NodeRecord)
A node is like a waypoint. It knows and stores its heuristic value, cost so far, and estimated total cost.
note: Cost so far is the cost so far from the start to this current node we’re on. Estimated total cost is cost so far + heuristic value.
Estimated total cost = Cost so far + Heuristic value
F = G+H (from other text book – same thing)
Connections (or Edges)
Connections connect nodes together. Connections have costs which is generally the distance.
Heuristic
The heuristic can be implemented as a class. Has a method that returns the heuristic value. Use integer?
Notes in dot point:
- Pretty much the same as Dijkstra’s algorithm, just with a heuristic.
- A heuristic in this context is a guess of the estimated cost from the |current| node to the |target node|. The most well known and simple is perhaps the Euclid heuristic, which is just the “as the crow flies” distance from the |current node| to the |target node|. Problems – can underestimate distance esp. indoors.
- Implemented in a loop (double loop – a while and a for). You iterate through nodes.
- Need a list to store open and closed nodes.
- Simplest implementation of a graph for A* pathfinding would be grid-based. Then you have just diagonal, vertical and horizontal connections. All diag. lengths are the same, and all vert. and horiz. ones are the same length.
- G and F need recalculating along the way.
- Instead of having a node “pointing” to its parent node, just have a LIST of the route so far? Both ways are fine. (Millington/Lester)
A* Pathfinding Steps:
- Add start-node to the open list. REPEAT FOLLOWING:
- Look in the open list. Which has lowest estimated total cost value? This becomes your current node.
- Remove the current node from the open list and add it to the closed list.
- FOR all outgoing connections from this current node:
- IF NOT passable OR on closed list, THEN ignore
- IF NOT in open list, ADD to open list. Make the current node the parent of this node.
- IF in open list already, check to see if the path to that node has a smaller cost-so-far. If so, that’s a better path. So make the current node the parent of this node.
- STOP if target node is added to the closed list (i.e. path found) OR open list has nothing in it anymore (i.e. no path found)
- Get the path either by using the parent node method, or you would have a list with the path in it by the time you get to the target.
- Reverse the list.
- Finish: You now have a list with the nodes in correct order, from start to target.
To graphically represent this, use draw a simple grid. The movers are just circles that move from one node to another. Or simply just draw the path as a line from node to node (i.e center of square to center of sqaure). Language: Java. Reason: Familiar/Solid language.
The movers will need to have steering behaviours (and to avoid each other if there are multiple movers). The main thing however, is to get the mover to seek from node to node. The seeking will cause abrupt changes in the mover’s path. How to fix?
To-Do-List: Before the AI exam May 28, 2007
Posted by deltawing in Uncategorized.add a comment
- Create A* pathfinding in Java = 2 days
- Implement the “separation” steering behavior in Java = 2 days (use Steering Forces)
- Read Goal-Oriented Decisions lecture notes thourougly.
- Other lecture notes – read
Optional: Combine steering behaviours.
AI is by far the most difficult subject I’ve encountered at Uni so far, so it requires a lot more work. It will also help make other programming subjects seem like child’s play. Isn’t that great!
The difference between “it’s” and “its”! May 19, 2007
Posted by deltawing in Uncategorized.add a comment
Whether you’re at school, uni or work, no doubt you need to write essays from time to time. Sure, the most important aspects in essays are the structure and the quality of arguments, the ideas, and the way it flows from one paragraph to another, etc.
However good grammar makes your writing look a whole lot neater and is easier to comprehend and understand.
Some will have achieved a very good standard of written grammar by the end of primary school, some later, and some never.
My year 10 teacher was vehement about grammar and the way it improved written legibility, and I just have to totally agree with him on this one. The one that tops my list is the different between it’s and its. It’s used incorrectly all the time, including all over my lecture notes from uni lol. Let’s remedy this 😉
its – This indicates possession. It is a possessive pronoun.
Example: The cat is grooming its fur.
If you had said, “The cat is grooming it’s fur“, you’d essentially be saying, “The cat is gromming it is fur”. That does not make sense.
it’s – Short for it is.
Example: It’s very windy today.
Now, here’s the complication. How do you indicate possession and plularity in nouns? Again, this is confused all the time. Apostrophes in this case denote possession, and without it, it indicates plurality.
Correct: Is that cat that’s sitting on the lawn Bill’s?
Correct: Is that Bill’s cat?
Correct: Is that James’ car?
Correct: Is that James’s car? Note: This is the same as the prior example, but less preferred.
Correct: The bird’s nest is perched on that tree.
This is my favourite:
Correct: The birds’ nests are perched up in those trees. Note: This just means – The nests of those birds are perched up in those trees. Or, the birds’s nests are perched up in those trees, although you would never say that.
INCORRECT: How many week’s until your birthday?
This is obviously incorrect and shouldn’t need an explanation! 🙂
INCORRECT: Is that Bills car?
That’s (that is) all for now. Perhaps I’ll code up a spell checker or a grammar checker when I get the time.
Computer words in German. Computer Wörter auf Deutsch May 19, 2007
Posted by deltawing in Uncategorized.add a comment
Versuch es mal bei http://german.about.com/library/blcomputD_T-Z.htm
Warzones Stuff May 19, 2007
Posted by deltawing in Uncategorized.add a comment
 Classes:
Main updated 10:00 pm 17/05/07
Entity updated 2:00am 18/05/07 This does not work with other classes. Have uploaded working one to source code
Projectile
Region/Zones updated 9:00 pm 17/05/07
AI updated 9:00 pm 17/05/07
Player new 9:00 pm 17/05/07
Python – passing lists into functions and copying them from one to another May 19, 2007
Posted by deltawing in Uncategorized.1 comment so far
regions = []
owner = “neutral” # which team owns this region?
def __init__(self, zones):
regions = zones
This works. Btw, zones is a list.
This code has an init function that accepts a list zones, and copies it into the regions list.
Convolution Matrices May 17, 2007
Posted by deltawing in Uncategorized.1 comment so far
Argh! Go to nail this for multimedia
Always use the UTF-8 charset for your webpages May 16, 2007
Posted by deltawing in Uncategorized.add a comment
Near the top of your HTML document for every page, make sure you’ve set the charset to UTF-8, as follows:
<meta http-equiv=“Content-Type” content=“text/html; charset=UTF-8” />
This will potentially save you a lot of trouble wondering why sometimes weird characters get displayed when working with PHP (or other web languages) and accepting and displaying user input, such as Chinese characters.
A Computer Science Blog 