Graphs & Resurrection

Calm down ladies and gentlemen! The blog's hiatus (which was essential for me to close the semester with a golden key) is happily over!

According to the post I wrote here, my free time is a geometric progression of negative common ratio directly proportional to the moment of the semester, therefore, the closer to the end, less free time I have. As a consequence of that, some of my most beloved activities had to be left behind so I could ensure the stability of my academic life, resulting in the abadon of the blog (but still being responsable for the joy of being approved in all the subjects).

But, as I am finally free of my responsabilities with college, I can return to the writing and research. And I have a lot to post about the projects and studies I participated on during my time of absence here. Starting with graphs.

As a college task I developed along with the great Nosirrahh and other two colleagues the base for the creation of an artificial intelligence in a tactical RPG battle system (like the awesome Shining Force II :D).

To be clearer, our objective was to create the root of something like that:

The system we developed creates a matrix of 50x50 cubes and generates obstacles randomly. From that the user can choose a search method and select if it will be limited or not. The system than calculates the fastest way between the capsule (representing the enemy) and the cube chosen as target, dodging all the obstacles.

Reaching the target

Five main classes were implemented for that:

• Nodo: Contains the information of position, index and children (adjacent cubes) of each cube.
• Lista: Compilation of Nodos for the execution of the search methods.
• MetodosDeBusca: Base algorithm for the app. Implements the three main search methods with or without a limit. Uses the Lista class and works with the children of each Nodo.
• Batalha: Generates the positions matrix and random obstacles. Receives a parameter that defines the number of lines and columns (in our case, 50 for both).
• GameExecution: Brings all the classes above together and organizes the execution of the game. Generates the cubes matrix according to the matrix generated by the class Batalha. Also draws the interface for the final user and executes the search method according the the selected parameters. It is responsible for the conection between the functional classs and the application itself;

There is also an article discussing the inclusion of graphs in games, as well as a deeper discussion of the execution of the functions above. The interested ones may check it here (Sorry, portuguese only).

And the application may be tested clicking here (there are still a few minor bugs, but nothing that holds back the program).

It was a short post and only a quick toe dive in the graph theory subject (the usability is semi-infinite and essential for games), but it served well as a pivot for the ressurection of the blog, that will go through an agitated and content rich phase now that I have time to return  to my activities and invest in new projects. Any doubts or suggestions, send me or the already mentioned great Nossirahh.

It's good to be back. :D