This entry was originally stored in my personal blog engine, but has been imported into WordPress.
Here’s yet another quick update that exploded into a large problem.
In this case, the issue was game controls. On the map screen, players need to move a character around. Originally, I used arrow keys. Since smartphones don’t have arrow keys, I added a D-Pad, a graphic representation of the traditional, 4-directional game pad. That way, smartphone users could use their thumbs, and web browser players could click on the pad.
The web-browser players were not amused. Practically every review of my initial game complained that the controls were “clunky,” and that it was awkward to have to click on the virtual representation of a game controller. I decided on a solution that ought to satisfy everyone – allow players to click/touch anywhere on the map, and the player would move there.
Unfortunately, this wasn’t as easy as it sounds. The enchant.js library does include a simple way to move sprites around this way, as you can see here, but there are limitations to this easy method. Namely, these examples all assume you’re moving a sprite across a clutter-less, continuous background.
Of course, my game is different. For one, there are obstacles in the player’s way. Second, although the movement is animated, it is not continuous – the player’s “location” is given by the square it happens to inhabit. The following picture – a game shot with a grid added to it – illustrates the problem well: you need to move the character from point A to point B, but you must stay in the squares, and you can’t move through the tiles that are blocked (by a building, fence, barrel, etc.).
The only solutions that came to mind involved a batch of “optimal path” algorithms I learned at university. These all involved complex branches and graphs of nodes and vertices, path costs, etc. Surely, I thought, there must be a simpler (and less computationally-demanding) answer. This was just a simple game, after all.
So, I looked for a shortcut. I thought I found one, an old algorithm I wrote during one of my lower-level (either CS II or III) classes. This was one of those “move the robot through the maze” programs. Using a slight variant of the right-hand rule, the program traced out possible paths. It pushed those moves onto a stack. If it ever found a dead end, it would pop moves off the stack until it found a different open path. When it got to the end, out went the stack and the robot walked out of the maze.
If my game screen was a big maze with one-square-wide corridors, I’m sure that algorithm would have sufficed. And it did move the player from point A to point B. Unfortunately, it did so in a manner like this:
After throwing the problem past a friend, I realized there was no shortcut past the optimization problem. “Use A-star,” he said. Who would have thought that I’d have to pull out my old artificial intelligence textbook to make a simple game?
* * *
Russell and Norvig’s standard may be an excellent textbook, but it’s a lousy reference book. Case in point: the the A* algorithm is first discussed on page 93 in the third and latest edition. If you’re looking to implement it, the textbook helpfully suggests: “The algorithm is identical to UNIFORM-COST-SEARCH except that A* uses g + h instead of g.” Flip backwards to page 84, and you’ll find the pseudocode for UNIFORM-COST-SEARCH. Underneath that pseudocode is another helpful notation: “The algorithm is identical to the general search algorithm in Figure 3.7â€¦.” That’s back further, on page 77. I found it easier, in the end, just to reread the whole section (skim sections 3.1 and 3.2, then concentrate on the relevant 3.3) to sketch out my own pseudocode.
I feel sorry for anyone trying to make sense of this textbook without a strong programming and/or computer science background. It assumes you know enough object-oriented programming to create a “node object” in code. It assumes you understand terms like “priority queue” and “pop.” And the algorithms are generic – you need to furnish your own definitions of “goal state” (for me, an xy coordinate), as well as, in A* terminology, the h(n) function (I used the distance equation between the current node’s xy location and the goal state xy). It all returned quickly to me; I’m not sure if it would to the average enchant.js programmer.
This may not be perfect code, but it forces your intrepid adventurer onto a reasonably certain path:
* * *
The A* program turned out to be the easiest part of my update. After all, I had to plug it into a movement framework that was originally made to capture actions from a keyboard or control-pad, not numbers unshifted from an array. Even worse – thanks to some “screen-centering” code meant to keep the player focused – the coordinates returned by clicking on the screen bore no relation to the map’s actual xy coordinates.
To remedy the latter problem, I had to add some calculations that basically undid all the fancy modifications made by the scene-centering function. For the former problem, I’m in the midst of dismantling the last of Evan Burchard’s original code.
All to move a character across the screen, because game players nowadays don’t want to use a directional pad.
All these code updates are making me fall behind actually writing the second installment of my game, a task where programming skills are of little use.