Tag Archives: array

When you wish upon A*, programmers will wonder what you are.

Image

Unlike sports or board games, the great thing about video games is that you can play it alone thanks to the AI; the Artificial Intelligence, presenting you with a challenge by means of opposing enemies. AI is in nearly every game, and as a result with our ever ascending technological breakthroughs, developers are blessed with the opportunity to further improve the AI, making them smarter and more capable, one day they will be smart enough overthrow us and enslave us, nothing to worry about, a kid born out of a confusing time paradox and a robot with a funny accent will save us all. Coincidentally related to the previous sentence, one of the many ways to implement AI is with the A* algorithm.

Image

The A* is an algorithm is a pathfinding and graph traversal that allows an object to follow something. This is done by planning out a traversable path between nodes. It uses a best-first search and finds the shortest (rather least costly path if you think in terms of Big (O)) from an initial node to one goal node. It follows the path of the lowest expected total distance basically whilst keeping a sorted priority queue of alternate paths.It identifies all possible routes that lead to the goal.

A* takes into account distances it already travelled; the g(x) part of the heauristic is the cost from the starting point. The formula for A* is f(n) = g(n) + h(n), g(n) is the cost of the starting node to reach n, and h(n) is the estimate of the cost of the cheapest path from n to the goal node.

Take this unweighted graph for instance:

 Image

We want A path 5 –> v1 –> v2 –> … –> 20

As such g(20) = cost(5àv1) + cost(v1àv2)+…..+ cost(à20)

A* generates an optimal solution if h(n) is an admissible heuristic and the search space is a tree, see h(n) is admissible if it never overestimates the cost to reach the destination node. It also generates an optimal solution if h(n) is a consistent heuristic and the search space is a graph as h(n) this time is consistent if for every node ‘n’ and for every successor node n’ of n, as such: h(n) <= c(n,n’) + h(n’)

Have you ever played a PC game where the computer always knows exactly what path to take, even though the map hasn’t actually been explored yet? Depending upon the game, pathfinding that is too good can be unrealistic. Fortunately though, this is a problem that is can be handled fairly easily.

The answer is to create a separate knownWalkability array for each of the players and computer opponents. Each array would contain information about the areas that the player has explored, with the rest of the map assumed to be walkable until proven otherwise. Using this approach, units will wander down dead ends and make similar wrong choices until they have learned their way around. Once the map is explored, however, pathfinding would work normally. F.E.A.R is an example of a game that uses A* to plan its search.

Image

I’ve programmed an A* algorithm before, it’s a basic but tremendously useful search algorithm that can be used from simple flash games to AAA titles, it’s like the Liam Neeson of algorithms. For the first time in your life you could get people to willingly come after you, well your game object at least. A programmer can dream can’t he?

P.S. you can thank Brett Gilespe for the joke in the title of this blog, that was a good one.

Advertisements

Klonoa and its distinct 2.5D camera system

Image

Klonoa: Door to Phantomile (and its Wii remake) is a side-scrolling platform game viewed from a “2.5D” perspective. The player moves the protagonist, Klonoa, along a path in a two-dimensional fashion, but the game is rendered in three dimensions. This allows the path followed to curve and for the player to interact with objects outside of the path.

 Image

The term “2.5D” is also applied (though mathematically incorrect) to 3D games that use polygonal 3D graphics in order to render the world and characters, but the gameplay is still restricted to a 2D plane or gameplay system. The term is rather loose as term because it generally refers to any game with 3D graphics that feature any sort of 2D playing style.

For example, the Crash Bandicoot games of the Playstation 1 were considered 2.5D because despite the 3D graphics, most levels are not as free roaming as its competitor at the time Super Mario 64. There were even some levels where you can only traverse left and right (except maybe a part at the beginning and end where you move to and from your goal).

Image

The main problem is that the assumption of Crash Bandicoot being 2.5D is based on shallow aspects such as level layout and camera perspective of those levels, I’m not saying they’re not important, but in this case those aspects don’t make it a 2.5 game.

Image

The New Super Mario Bros. are also considered examples of the sub-genre as it uses 3D models and animations, but other than that it’s strictly 2D, the 3D parts of it are mere aesthetics. Layout, design, play style and controls, all of it is 2D. Street Fighter IV is another game considered 2.5D for similar reasons due to its 2D gameplay coupled with its 3D rendering.

I consider Klonoa to be the purest example of the subgenre because the combined design of the level layout, the gameplay and especially the camera angle are all 2D with 3D elements thrown in which is essentially the textbook definition of the term.

Image

Like many platformers you have a camera that interpolates accordingly along with the character’s ever changing position in a similar manner to other popular platformers like Mario. However there are points where you will end up turning as the level is not a straight line, when that happens the camera remains parallel to the character while maintaining a certain distance throughout, which includes moments when your character jumps towards the screen which is an example of a dynamic camera angle.

I chose this game in particular because it’s an example of how camera dynamics can ultimately create a new genre in a sense. Like in movies, camera works don’t just provide a visual of the audience but a whole new perspective.