MsPacMan Artificial Intelligence


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:

clusters

The project is open source and is hosted on github. Feel free to browse the code and adapt it to your needs: MyPacMan.java

Without further ado, here you have the full report. Enjoy the reading!

NB: the report was rendered using LaTeX and the graphs where plotted using Mathematica 9.

Java, WebGL and cross-platform game development

WebGL

Web browsers are probably the most widely used software in desktops and mobile computers. They have become the swiss army knife of the Web 2.0 digital world and it is under this context that a Javascript API for rendering GPU-based graphics was born: WebGL.

Long live Java

The WebGL technology enables rendering complex 3D or 2D scenes such as games within your browser. You could write the next Angry Birds in javascript and WebGL. But why not leverage the power of existing Java technologies and write your game in Java using WebGL? Yes! You can write Java code and deploy it on the web as javascript thanks to the help of the Google Webtoolkit. (If you haven’t tried it, then you should!).

The following web app illustrates how easily Java and WebGL can be used together with Libgdx game development framework to create fancy 3D scenes.

Click on the image to see the webGL app. Note: you’ll need a WebGL compatible browser such as Firefox or Chrome.

Teddy bear

A screenshot of the webGL application.

Instructions: use the arrow keys to move the camera and drag the mouse to rotate the camera.

Notes about the code

  1. The code uses WebGL which is pretty much OpenGL ES 2.0.
  2. The sky and mountains background texture (a.k.a Skybox) are rendered using cube mapping and custom shaders.
  3. 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.
  4. The boat 3D model comes from here and the texture from here.
  5. The teddy bear comes from here (if you know the original source, let me know).
  6. All models were exported to G3DT format using blender.

NB. The code will be available on github in the coming days.

Edit: The code is available here: https://github.com/recastrodiaz/java-webgl

Cross-platform game development

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 FormGrabber, IV – Who’s guilty and Conclusion

Who’s guilty ?

Both Firefox and Windows are to blame for.

Firefox

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

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

Firefox FormGrabber, III – Code Injection

How does it work ?

Proof of concept

The proof of concept is open source and can be found here : https://github.com/recastrodiaz/formGrabber/. It includes instructions on how to run it on your machine.

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”.

Firefox Hooked

Facebook HTTPS has been compromised. Users's Email and password are sent in clear text to localhots/postDemo.php

Continue reading

Firefox FormGrabber, II – Definitions and Firefox internals

FormGrabber

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.

Continue reading

Firefox FormGrabber, I – Introduction

Introduction

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.

Authors

  • CASTRO Rodrigo
  • COQUET Matthieu
  • SAUVAGNAT Xavier

Continue reading

The COTBLEDTCID approach to object detection and pose estimation, Part V – Circles detection

Introduction

Let’s do a summary of what we have done so far:

  • 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.

Continue reading

The COTBLEDTCID approach to object detection and pose estimation, Part IV – Transformation

Introduction

With the last step we know where the bottom edges of the pawn are located on the image, we just need to find a way to transform the coordinates of those pixels into game field coordinates.

Given a point p' from the Image plane, we’d like to transform it into p from the Game field plane. We can write:

p = H \cdot p'

We observe that straight lines are kept straight, thus H is called the homography matrix which can be computed if at least 4 different matching points are given for both planes. (p1 \leftrightarrow p1', p2 \leftrightarrow p2', p3 \leftrightarrow p3', p4 \leftrightarrow p4')

HomographyIt’s worth noticing that both p and p' points are given in homogeneus coordinates.

Continue reading