Reading for the next couple of weeks
Read this pdf which has a simpler explanation of A-Star. Also please read pages 238-255 on world representation for A-Star. Also read pages 293-309 on decision trees.
Recent Comments
-
Recent Posts
Meta
No class 4/20/10. Assignment due.
There is no class… However 6PM 4/20/10 is the last chance to hand in the assignment ( the state machine one). I suggest doing some of the extra credit as handing it in this late means a 15 point penalty.
I am missing the assignment from everyone who didn’t show up for class on 4/13/10. There is only one way to hand it in and that is to email it to me. If it is too big just zip the .cs files and send the zip.
Something to think about is who you want to team up with on the final assignment. It will be team based.
The final assigment will be due May 11th at 9pm. That gives us 4 classes to work on it if we don’t count tomorrow. The requirements for the assignment aren’t final yet but it will be a mini game where you must incorporate everything taught up until today. This includes unity scripting, steering behaviors, state machines, and path finding. Each piece will be worth some percentage of the project. And of course there will be extra credit. But that will be to include the topics covered after today… Decision trees and behavior trees.
A-Star Implementation/Playground
Here is an online version of an A-Star Pathfinder in Unity3D. Here is a link to the source. Please play with it and look at the source. The source is close but not identical to the code in the book. The code in the book was incomplete and wouldn’t run as is.
I just updated the sandbox to include a variable “heuristic”. In this case it is just a float that scales the distance calculation to the goal. When it is zero A-Star is equivalent to Dijkstra. Notice as the value gets higher the search spreads out less and searches fewer nodes. However as it narrows it can return a non-optimal path. But if you play long enough you can see that some non-optimal paths still look intelligent and plausible.
Assignment due today(4/6/10). Lecture is going to be online.
Do not go to the classroom. The lecture is going to simply be to look at a sample implementation of A-Star that I am going to post tonight. It will be close to the pseudo code in the book. It will also have a grid that you can interact with and watch the algorithm work. You will be able to choose obstacles and start and end points.
Articles on A* and World Representation
Most linked to article on A-Star I could find.
http://www.gamedev.net/reference/articles/article2003.asp
Article on A* and search written way back in 1999 on parchment paper.
http://www.gamasutra.com/view/feature/3317/smart_move_intelligent_.php?print=1
Article on Navigation Meshes for use with A*:
Next Week(3/30/10)
It was just brought to my attention that next week is a religious holiday for me. So what that means is that I will not be giving a lecture on 3/30/10. It also means that you can hand the assignment in up until midnight on 3/30/10.
Also for the following week (April 6th) please read about path finding. We are going to cover A-Star in class. It will help if you have some idea of what it is before I start talking about it. This corresponds to pages 197-237 in the text.
No Class-Assignment
This should be easy. Take the code from last class and make the birds flee you(the player). Due at the end of class next week(you will be able to work on it during class next week).
Extra credit:
Implement a vision cone for the bird. Right now they see 360 degrees. Hint: Use a dot product on two unit length vectors. Remember the dot product is equivalent to a cosine of the angle if the vectors are unit length.
Implement any interesting behavior using state machines that you want. This is a chance to get the birds to do whatever you feel like working on. Have some fun.
State Machines – After Class 1
Here is the code we ended up with after our first lecture on state machines.
State Machines
For tonight I have put together a revamped and extended version of what we have been working on in the past. Here is a link to it. Tonight we are going to go over state machines. We are also going to briefly go over perception systems and blackboards, both of which are in the code.
See you soon.
Something to play with until we meet again
We are on spring break next week. But if you want, this is optional, you can play with the project I just uploaded. It is basically the last assignment but with real animations added. What you can do is try to get the animations to play correctly according to what the actor is doing. Such as walking when going slow, running when going fast and not abruptly changing direction.
Have fun!