Over the weekend I had the idea to create an app which creates a random sandwich for you to get at Wawa. The result is the Sandwich Roulette! Here’s the source on Github.
For the last assignment for CIS564, we created a simple tag/hide-and-seek game using path-finding, and the behavioral steering from the last assignment.
A* (A-star) is a path-finding algorithm which finds an optimal path between two nodes given a cost function which yields the distance from the start and a good heuristic estimating the distance to the goal. The game field is divided into a grid of 1600 squares. Each square is marked as open or obstructed, based on the presence of a mushroom obstacle. Obstacles may be placed dynamically by holding ALT and LEFT-clicking with the mouse. In Path-finding mode, Lenguins will plan a path around the mushrooms to the target.
Mushroom obstacle
The algorithm was implemented in C++ and compiled in XCode to a OSX Bundle for use with Unity. I turned out to be the only one to work on OSX. Since a Visual Studio project was required, I ported the code over to Windows after I was sure it worked. I’ve noticed interesting differences in the way the code works in OSX versus Windows–or it could be a difference in compilation between XCode and Visual Studio. For example, I was using a route where I subsampled a list of vectors that represented an agent path. I had something like:
std::list<vec3>& Environment::subsamplePath(std::list<vec3>& path, int factor) {
int i = 0;
for(std::list<vec3>::iterator it = path.begin(); it != path.end(); ++it) {
if(i % factor == 0) {
path.remove(*it);
}
i++;
}
return path;
}
This seemed to work fine on OSX, but Windows threw a fit. Unity would immediately crash when I ran the game. I traced the problem to this function and a little investigation shed some light on the matter. When you call remove, it invalidates the iterator–makes sense. So I changed the code to the following:
std::list<vec3>& Environment::subsamplePath(std::list<vec3>& path, int factor) {
int i = 0;
for(std::list<vec3>::iterator it = path.begin(); it != path.end(); ) {
if(i % factor == 0) {
it = path.erase(it);
}
else {
++it;
}
i++;
}
return path;
}
Clicking the “Hide & Seek” button will enable the Freeze Tag mode.
Game Options
You control a player and may select various camera control schemes.
Camera Modes
The AI-controlled Lenguin agents head towards various hiding spots placed on the map. New hiding spots may be placed using SHIFT + LEFT-click. They appear as blue spots on the map. Each Lenguin will head towards the nearest hiding spot. Once a Lenguin reaches a hiding spot, it will claim that spot, and other Lenguins which were seeking that spot will acquire a new target. The process repeats while there are empty hiding spots.
When the player comes into an agent’s line of sight, the agent will flee away from it. If the player is able to tag the agent, it freezes in place.
Frozen Lenguin
Non-frozen Lenguin agents will attempt to tag the closest frozen agent. If the tag happens, the Lenguin is unfrozen. The game ends when the player freezes all the agents. Then, the game restarts and play continues.
Game Field
Here’s a progress log that I started but neglected to finish:
My most recent assignment for the Game Design class I’m taking is to implement some behavioral animation steering behaviors. The task was to implement steering behaviors such as: seek, flee, separation, avoid, follow the leader, and flocking.
We were provided a framework featuring Lenguin characters
A gaggle of lenguins
and a menu like this:
The in-game menu to choose steering behaviors
and entry points to call a C++ dll that would return force and torque vectors given agent properties and world data. It was a really interesting exercise, and it’s always tricky and fun implementing algorithms. One of the more difficult ones was the avoid behavior, which allows agents to go around obstacles
Lenguins avoiding obstacles while seeking
This is done by detecting a collision with an object, and adding a tangential velocity to the agent’s current velocity, allowing it to walk around an object, hugging its radius. This was both an exercise in implementing algorithms and using Unity’s native plugin capability. Although the Framework was provided for Visual Studio, it was fairly straightforward to port it to XCode, and Unity allows OSX users to compile native plugins into Bundles.
One of the weirdest things I found is when I went to port my XCode c++ back to Visual Studio, I was getting crazy velocities back. It took me a couple hours to discover that the default constructors for the vec3 structures, which store the values in a float array, did not initialize the array values. It’s odd because this worked fine on XCode/OSX, and I’m wondering if XCode did something special with the array values, like initialize them to 0.
Here’s a short video of the Lenguins in action:
Here are links to executables if you’re interesting in trying yourself. Use ctrl-click to move the target, and click on the Behavior menu to change the behavior.
This week I was in San Francisco participating in a Wharton class about innovation. We had a week to sort through various ideas for web products and create a prototype. I worked on two projects. One is a lottery site, with a simple demo available. I got to use the Youtube API for playing a video and then performing some action upon completion. It was  a little clunky to get setup, but afterwards worked flawlessly.
The other was an idea for a social dashboard for restaurants to keep them up to date with the latest reviews on sites like FourSquare and Yelp. I worked with a great programmer named Sean, who worked mostly on integrating the 3rd-party APIs. It was a Rails app that we pushed to Heroku.
I’ve been working on some homework for computer vision. It’s such an interesting class because of how rich the visualization of my code results can be. Matlab has also been a real pleasure to work with. Everything is well documented and the IDE has features I haven’t seen in other IDEs. I am working on an assignment in edge detection.
There are several steps required including performing a convolution of the image with with the derivative of the Gaussian, determining the magnitude of the gradient, and using it to find local maxima (in terms of intensity) of the image. That’s the part I’m at right now. Instead of using the x and y components of the gradient to compute edge orientation, I just determine local maxima by querying all the pixel neighbors of each pixel. This was quicker and helped me to make sure my code worked. Here’s the magnitude of the gradient of the image and the local maxima as computed by my algorithm. They’re very bad points for edge detection, but I’m happy I get something resembling the shapes of the image! One step at a time.
I’ve been doing some homework for Computer Vision class. Matlab apparently has extensive image processing capabilities. One handy function is “edge” which will return a zero-filled matrix with 1s corresponding to edges.
From left to right, top to bottom, the methods of edge detection are: Sobel, Prewitt, Laplacian of Gaussian, Canny, Roberts, and Zero-cross
I used jQuery for the UI. I am a recent convert to jQuery, having mostly used Prototype + Scriptaculous.
The word list is embedded into the page script as a javascript array. On document ready, html is generated, which writes the first and last word to the page, and creates blank input boxes for the intermediate words.
There is a keyup event bound on each input box, which will determine if the word is correct. If it is, a css class will be added which shows a green underline underneath the box. Otherwise, a red underline will be shown.
Finally, there are buttons on the page which are created dynamically and provides hints or reveal all of the answers.
Word Jumble Filled
The problem of generating the chain of clues is a simple search problem. In this case, depth-first search was used, because the algorithm would attempt path depth-wise and only explore another branch if the generated chain was not long enough.
Another tactic would have been to use a breadth first search. To use breadth-first search, we could have modified the regex pattern to find all words that differed from the base word by just one letter.
Using water as the base word, that regular expression looks something like: /([^w]ater|w[^a]ter|wa[^t]er|wat[^e]r|wate[^r])/. This would find all words in the dictionary that differed by one word (let’s call this word set B).
If we were using breadth-first search, we would then repeat the process with all of the words we just found (word set B).
If you were to visualize the difference between breadth-first and depth-first search, breadth-first would look like a tree with wide but shallow roots. Depth-first search would look like a tree with few but deep roots.
The flexibility of the puzzle is enhanced by optional query parameters that may be applied. The word param allows specification of the starting or seed word. The length param specifies the maximum length of the puzzle.
The program uses recursion to perform the search. This almost goes without saying, for it is difficult to do general search without recursion (although you could do so with macros and similar programming constructs). Search may be done using loop control structures but I can’t imagine an elegant solution using loops.
The pseudocode for the recursion is basically:
function build(baseWord, chainWords, maxLength)
regex = generateRandomRegex(baseWord)
wordSetB = getPossibleWords(regex, notIn=chainWords)
for(word in wordSetB)
chain = build(word, chainWords+word, maxLength)
if Length(chain) >= maxLength
break
return chain
The first thing I did was made sure that the word list would be cached on application start. This was as simple as creating an Application.cfc cfcomponent and implementing the onApplicationStart function. This function reads the dictionary in (described in the last entry) and caches the word list in a ColdFusion array. There are other options for storing this data, but this had the best mix of speed and function considering the method of search I wanted to use against it.
Although the dictionary was only 52K, this caching probably helped performance a great deal.
To generate the word list, I decided on the following algorithm:
Example:
word: water
regex: w[^a]ter
There are a few considerations not discussed above in generating the puzzle:
In my last entry, I described the concept behind the Word Jumble game. In this entry, I will describe initial steps in creating the game.
Firstly, I needed some dictionary of words. The Unix flavors have built-in dictionaries, and I develop on OSX, so I Googled the location of its dictionary:
/usr/share/dict/words
I knew I wanted to do puzzles of only 5-letter words, so I used the
grep
command to create a file of just these words.
grep ^.....$ /usr/share/dict/words > dictionary-5letterwords.txt
Notice the regular expression I used. I wanted to demonstrate an actual use of regular expressions for this project. The regular expression
/^.....$/
says to match a line of just 5 characters. The period means to match any character. I made the assumption that there would be no words in the dictionary with a space or other punctuation–although that was, perhaps, a faulty assumption.
Next, I started working on the code. Since we use mostly ColdFusion at Wharton, that’s what I wrote the app in.
Word Jumble Filled
