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
Programming on PS Vita is really easy. Sony has done a lot of efforts to please the indies developers since this generation of console. They understood that more indie games can make the players wait between the blockbuster games.
Programming on PS Vita is done in C#. So if you’re already used to programming on Xbox 360, XNA or Unity, you won’t have trouble.
In the SDK Bundle Sony provides, you will find a Integrated Development Environment (IDE) very similar to Visual Studio. In fact it looks like a lighter version of Visual Studio. In the bundle, there is also a lot of very interesting samples showing few abilities of the handheld and the framework
All you have to do to get you started is to follow these steps:
1) Register / Sign-In here: https://psm.playstation.net/portal/en/#register
2) Download the SDK Bundle.
3) Start coding/ fiddling around with the libraries
4) If you want your code/game to work on your PS Vita (because an emulator/simulator is never 100% faithful to the actual hardware), you will have to subscribe for a license on the same website quoted above. This license will give you a key and will allow you to publish on the PS Mobile Store.
All these steps are for the PS Mobile Store which is also available on some other selected Sony devices. I’m sure if you’ve got something awesome coded on that, you can negotiate with Sony to publish it on the PS Vita Store.
Here is a tutorial I used to get started doing things on my handheld:
In the interesting channel family on youtube, here is ASAP Science.
Created by the biologists Mitchell Moffit and Gregory Brown, the channel explains a lot science facts with videos of drawings in stop motion. They are followed by millions of youtubers all around the world.
But who’s better than them to explain their work: