View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Case Final Project Summer 2007

Path finding

OTIB Path Finding
1. Introduction
If you play our game, you can easily see that characters do not simply teleport or move straight to a tile. Instead, whenever an order is given to a character, let’s say pick up an item, he will check to see if he is right next to the item or not. If not, he will find the shortest path to the tile that the item on. We use BFS to do the job.
For the sake of our pretty GUI, method isWalkable: at: in Location is always returning true. This enables Sim characters to move on anything, so you cannot see how robust our path finding is. However, if you are interested, you can change the last return statement in isWalkable: at: to false. This might cause some parts function incorrectly but the path finding feature will run as expected. You can actually create a maze by putting bookcases on the floor and order the character to move through the maze... and watch out for the good stuff :)
The idea of creating a maze came from the fact that one of our members was a fan of prince-princess-evil story. He wanted to be a prince and CS female students to be princesses. The prince’s objective is to find the way through a maze (Common area, States Lab) to rescue princesses from the evil CoC and take (each of) them out on a date :-D

2. Implementation
findPath
"Find path from coordinates to destinationCoordinates"
|q f l current next matrix found|

"reset current path"
path _ nil.
last _ 0.

"initialize a queue"
"it is better to initialize the queue whenever you create a person since one person only need one queue to find path"
q _ Array new: (location width location height + 1).
f _ 1.
l _ 1.

"put the position where the person is currently on into the queue"
q at: f put: coordinates.

"has not found the path"
found _ false.

"create a matrix based on the current location, see createMatrix"
matrix _ self createMatrix.

"BFS"
[f = l and: [found = false]] whileTrue:
[
"take the first element out of the queue"
current _ q at: f.
f _ f + 1.

"look for 8 tiles around to see if the are available"
(1 to: 8) do:
[
: i|
next _ current + (NextCoordinate at: i).
((location inBounds: next) and: [(matrix at: (next x) at: (next y)) = 0]) ifTrue:
[
matrix at: (next x) at: (next y) put: current.
l _ l + 1.
q at: l put: next.
(next = destinationCoordinates) ifTrue:
[
found _ true.
]
].
].
].

"if there is a way, trace the path from source to destination"
found ifTrue:
[
current _ destinationCoordinates.
path _ Array new: (location width location height).
last _ 0.
[current = coordinates] whileFalse:
[
last _ last + 1.
path at: last put: current.
current _ matrix at: (current x) at: (current y).
].
]
"mark that there is no path"
ifFalse:
[
destinationCoordinates _ nil.
finalMessage _ nil.
].



3. Conclusion
We wanted to put so much on the path finding like adding items that increase speed of characters. That means the shortest path at on moment might not be the shortest path overall. Simple BFS will not be able to handle this. Dijkstra or A might be a good solutions. We leave this open for you to discover.

Link to this Page