After taking the course CS7032: Agents, AI & Games at Trinity College, Dublin. We were asked to design and implement an artificial intelligence algorithm for the famous PacMan game, under the rules of http://pacman-vs-ghosts.net/ (Which seems to be down as of now) and using our knowledge of abstract architectures.
We could choose to design either the behaviour of Ms PacMan or the phantoms. I though implementing Ms PacMan AI would be “faster” as there’s only one entity to design. Never have I been so wrong. It took me around one week of spare time to get it right. Though in the end, I got some acceptable results.
The core AI algorithm is inspired by reactive agents and the evaluative feedback approach. I ran around a thousand games with multiple strategies and identified the best one by plotting the score histogram. The results are on the report.
One algorithm which I found particularly interesting is “Clustering regions by connected components”, which is a linearithmic algorithm with respect to the number of components. This algorithm has certainly many different use cases outside the PacMan world. I explain this algorithm in the report. A screenshot showing the pills clustered by region:
The project is open source and is hosted on github. Feel free to browse the code and adapt it to your needs: MyPacMan.java
Long live Java
There is one shader program for rendering the water which is based on the excellent Jay Conrod’s water simulation shader. The water looks jaggy because there aren’t many triangles in the model. Feel free to change this.
The boat 3D model comes from here and the texture from here.
The teddy bear comes from here (if you know the original source, let me know).
All models were exported to G3DT format using blender.
NB. The code will be available on github in the coming days.
The holly grail of developers is to code once and run everywhere. Unfortunately, this is hardly true as platforms are extremely different from each other. Furthermore, screen sizes and input devices are not the same. Nevertheless, the Java ecosystem provides great multi platform support out of the box. Add GWT and Monotouch to the mix and you’ll support Mac, Windows, Linux, Android, HTML5 and iOS from day one. Check the following cross-platform gaming frameworks to see how it can be done: PlayN and Libgdx.
Firefox simplifies the process of finding the target function PR_Write as it is inside a dll, compromising the security of the web browser.
Windows lets our malicious FormGrabber interfere with the normal Firefox’s workflow without asking any questions. It lets our process execute code within Firefox’s Virtual Address Space and more importantly it lets our malicious process change segments of Firefox code. Continue reading →
The POC (Proof of Concept) has been successfully tested on Windows XP SP3, Windows 7 32 bits and Windows 7 64 bits with Firefox 11.0 and 12.0. Nevertheless, it has failed to work on at least one Windows 7 64 bits computer.
The following image shows an example of network connections created by Firefox when logging in to a Facebook account. The first line represents the encrypted data sent over a secure tunnel between the web browser and facebook.com (namely HTTPS). The second is a copy of the first but sent in plain text to localhost/postDemo.php. It contains the User’s email and password : “myMail@mail.com” and “guessMe”.
Facebook HTTPS has been compromised. Users's Email and password are sent in clear text to localhots/postDemo.php
Almost every sensitive information, such as passwords, login credentials, bank account numbers, credit card numbers, etc, is sent from your web browser when you fill an online “form” to a secure remote sever trough the web standard HTTPS POST.
A form grabber is a malicious code that intercepts POST data coming from web “forms” before the encryption takes place, thus avoiding the added security of the https protocol.
The following series of posts represent the completion of a university research project and a compilation of what has been said at INSA de Lyon the 26 of April 2012. You can find the slides here. I highly encourage you to read these posts while browsing through the presentation.
I am not responsible whatsoever of the use or misuse of the information hereafter. Be wise.
COT: colour thresholding. We separated yellow objects from the rest.
BLED: blob edge detection. We retrieved the bottom edges of blobs (pawns).
T: transformation. We transformed the image’s pixels into game field points (aka. pixels to meters).
And the last step CID: Circles Detection.
As you may have already noticed, pawns and tower of pawns are in fact circles when viewed from above. Therefore, the bottom edges we found with BLED are also circles’ segments when transformed into game field coordinates (step T). This is the property we’re exploiting below.
There is still too much information we do not need on the B&W image we got on the last step. That’s why we need to extract the features we do need. One way of accomplishing this is by performing a connected component analysis in binary images, aka blob labelling. However as you’ll will see, this method is not completely adapted to our needs, so a new approach is proposed: Blob Edge Detection.
Images are usually too complex to be treated by computers as is. In most cases, they have to be enhanced and simplified before any algorithm can be applied on them. Fortunately for us, the rules of the contest specify that yellow is the colour of pawns and figures we are looking to detect.
Generally speaking, the purpose of Colour Segmentation is to extract information from an image by grouping similar colours. In our algorithm, we implemented colour segmentation by thresholding yellow colours, that is to say, the computer builds a black and white image from the original image where white colour represents yellow colour and black is everything else. This is called colour thresholding.
The problem is, as you may have already guessed, the notion of “yellow” colour. For humans, it is relatively easy to tell whether a colour belongs to a group of colours, but for computers this is a whole different story.