Using sprites from Super Mario World (SNES) and Super Mario All Stars, students at the University of Tübingen in Germany, reproduced behaviours of the quoted games in a program.
They added some artificial intelligence to Mario so he behave by himself in this world. For example, sometimes when he is hungry, he will go to a “?” Block, make a mushroom appear and go grab it.
Follow me on Facebook : RockMarc
Or on Twitter : @DebuggingWorld
Share if you like the content of this blog.
Pathfinding is the art (let’s use big words here 🙂 ) of finding a path between two points : a start and a goal.
It’s a whole field of artificial intelligence in computer science.
You can find pathfinding uses in robotics, GPS navigation systems and video games.
Pathfinding uses algorithms to compute a path.
Algorithms are a “step-by-step procedure for calculations” (source: Algorithm article on Wikipedia). Basically it’s a set of instructions for the computer to execute a specific task.
In video games, pathfinding is used to give directions to non-playable characters (NPC) most of the time. It’s also used in real-time strategy (RTS) games or in massively multiplayer online role playing (MMORPG) games where the player can click somewhere on the screen and his character will go to the destination clicked.
But how does the computer know where the player has clicked?
In a 2D game, all the screen coordinates have an equivalent in the game map.
In a 3D game where you can move the camera, a straight ray is projected from the click position toward the closest obstacle.
Also how does the computer know where a character can walk, move in a game world?
You have to specify it thanks to an abstract structure. It’s a set of data that’s abstract because the player can’t see it during normal play. (there’s a lot of other abstract structures in video games to help developers map events in the game levels)
Here are some of the most used different type of abstract structures for pathfinding:
The default one and simplest to understand. Unfortunately this one needs a lot a tiles to take into account obstacles which are not rectangular. And when we need more tiles, we need more computation.
It’s a grid… but made only of triangles. It’s much better to take into account obstacles
The more limited one. In this one, characters only move on straight line predetermined.
– Navigation mesh
The most recent and used one. Here characters move from area to area. In each area they can move freely in straight line to any point. To move to another area, they must reach a point near the intersection of the current area and the next one.
Most of the time, these structures are in 2D even in 3D game, to make it easier to do the computation for both the developers and computers. The speed of reaction of a character or a unit must be very quick so the player doesn’t lose patience. So sometimes it’s even better to use an algorithm who find a good-enough path between two points than a slow algorithm who will find the shortest path.
But we can divide pathfinding algorithms in 3 types:
– The ones to find the tiles to use in the abstract structure
– The ones finding the way in the selected tiles before. So it will determine by which point and how it should cross each of the selected time. It seems easy but it’s not. (more on that in a next post)
– The ones smoothing the path determined by the previous algorithm. Depending on the unit moving, if it’s a human character we can make it turning in curbs instead of straight angles, going straight instead of zig-zags, etc.
All of this, is meant to give you an outlook of what pathfinding is. I hope it interested you. I’ll probably write more about it in a future post.
To end this post, this is what happen when pathfinding is not correctly done in video games:
– “Path Search Demo” software from Bryan Stout
For me, artificial intelligence (AI) is a branch of computer science that try to reproduce part of human behaviour or abilities with a computer.
Artificial intelligence is often seen in movies on the form of robots behaving like humans or a computer who becomes crazy and is taking control of every electronical or electrical devices.
In video games, AI is either used to describe a game that can take decisions by itself or to designate some algorithms giving a behaviour to some characters, units, objets.
Video games with a “true” AI (who can deduce decisions) are rare because it takes a lot of research of development and consequently money to realize. Also having an AI in a game won’t guarantee it will be fun to play or that it will sell a lot.
Here are some things you can do with AI:
– Tutoring actual students
– Pathfinding (more on that in a next post)
– Learning how players behave in a environment to create non playable characters who mimick them
– Having a conversation with a human:
The famous Alan Turing’s test places a person in front of a computer. This person will communicate through the computer with what he believes is another human. It’s in fact a machine adapting to the dialogue with the person by answering properly.
– Processing natural language.
– and a lot more…
Each of this task is very complex and there is a lot of research going on in universities and companies about each of them.
However this is one of my favorite computer science subject.
I just find it thrilling to learn more about that.
Unfortunately, there is a lot more to be done and it’s hard to find recent articles about it.
If you want to read more about artificial intelligence there’s AIGameDev which gives an outlook of what can be done.
Also if you want to work in that field, your best bet would be to work in universities.
It’s a fascinating field with a lot of concrete applications.
Source of the image: