Touch events on the pathfinding pages

(On this blog I'll sometimes go into the “making of” the game programming tutorials I post on my site.)

For my pathfinding pages I wanted to support "painting" on the map to make or erase walls. When you change the map, the pathfinding algorithm updates the paths. Here's how paint works:

Set up mousedown, mousemove, mouseup event handlers on all the tiles.

1. When you press the mouse button, I toggle the tile you're pointing to.
   


2. When you move the mouse, I set the tiles you pass over to match the tile you first clicked on.
   


3. When you release the mouse, I stop tracking the mouse.
   

For example, if there are three tiles A B C and you are over A without a wall, then press the mouse button, I put a wall at A (toggle). If you then move the mouse over B, I make B a wall (set to whatever A has). And then if you release the mouse over C, I'll set C to a wall as well.

When I first published the Introduction to A* article two weeks ago, I still had an item on my bug list to fix map editing on a touch screen. I wasn't sure why it wasn't working. I figured the touch events touchstart, touchmove, touchend would map cleanly to mousedown, mousemove, mouseup. But they didn't. After some debugging, I figured out that the touchmove and touchend events get sent to the object that received the touchstart event. That means instead of seeing A.mousedown, A.mousemove, B.mousemove, C.mousemove, C.mouseup, I am seeing A.touchstart, A.touchmove, A.touchend. I don't receive events on B or C at all.

To fix this, for touch events I look up the x,y position of the touch and map that back onto a tile. This is sort of annoying, as I figure browsers already have a way to map pixel locations to SVG DOM objects, but I don't know how to harness that lookup. Fortunately, most of the diagrams are simple square grids, so the code to map pixels to grid locations is easy.

There are some more tweaks for the page to work well on touch screens, but it should mostly work now.

Read More

Pathfinding on isometric grids

People sometimes ask about pathfinding on isometric grids. This is the wrong way to look at it.

You're finding paths in the game world. Isometric is not part of the game world. Isometric is how you look at the game world. Consider the shortest path from New York to San Francisco. Does the shortest path depend on how you hold the map? No! The person looking at the map does not matter. The shortest path is the same no matter how you are looking at the map.

Here's an animation showing the way to think about isometric grids. Note that the map coordinates and the path don't change; it's only the way we look at it that changes.

0,0
0,14
14,14
14,0

Pathfinding runs on the game map. The game map coordinates shouldn't depend on "top down" or "isometric".

Read More

Support the development of the Terra Centauri RTS

Not exactly hot of the press, but the developer behind the MegaGlest based RTS Annex: Conquer the world has started a new project:

In a lonely planet circulating a distant star, a war of survival rages on. There a sentient race, the Valkyries struggle to protect their world and themselves against the parasitic organisms Devourers. Explore large maps for resources, treasure, and other advantages to fight back the relentless horde of Devourers.

Terra Centauri: The Last Stand is a new unique MG based game. While game shares a similar art style to Annex, this game has radically different gameplay and much higher quality models.

He is also running a funding campaign on Patreon and you can give feedback on the Megaglest forums.

Speaking of Megaglest: while development has slowed down a bit lately, the work on the CE-GUI based new menu and HUD is looking great.

Read More

New Introduction to A* page

I've been working on updating my pathfinding articles with interactive diagrams. While doing so, I realized that I don't like the way I've presented information in my pathfinding articles. Instead of just updating them in-place, I'm writing new tutorials and will eventually figure out how to stitch everything together.

A big one I've been working on is the introduction to A*. I started writing these notes in 1997 and have updated them over the years. The past few months I've been working on a replacement for this page. The page compares Breadth First Search, Dijsktra's Algorithm, Greedy Best First Search, and A*. Differences from the old page:

• All the diagrams are interactive (of course)
  


• I mention non-grids a little more (still not enough)
  


• I use contour lines to compare the algorithms (not sure if this will make sense to people)
  


• I show working Python code for each of the algorithms
  


• I have supplemental material that includes the helper functions and classes needed for the search algorithms
  


• I give some guidance on which algorithm to use
  

There are lots of little things (smoother animations, touch screen support, better code highlighting, better contour line visualization) that remain, but I decided to publish it 90% complete instead of delaying it to polish all those little details. Take a look at the new introduction and let me know what you think. Is it understandable? Do the contour lines help? Is it enough to help you implement A* yourself?

Read More

Duck Marines, FOSS remake of ChuChu Rocket

Thanks to Tangram Games for pointing out to us that they just released version 1.0 of their local multiplayer game Duck Marines.

They describe it as:

Duck Marines is a cross-platform free software PC remake of Sonic Team’s ChuChu Rocket.
Duck Marines attempts to recreate the magic from the local multiplayer of ChuChu Rocket while adding new elements like mini games, a level editor, colorful pixel art and more.

But see for yourself:



For those not familiar with the original on the Dreamcast here is a small description of the gameplay:

The goal of the game is to get as many ducks into the submarine of your color. Gray ducks give you one point, gold ducks give multiple points and pink ducks will trigger an event or mini game.
Guide the ducks towards your submarine by placing arrows on the ground. When walking over an arrow ducks will instead walk in the direction the arrow is pointing.
Beware of the blue predators. Predators love to eat ducks and will kill a large number of your ducks if they reach your submarine. Try instead to guide the predators to the other players’ submarines using your arrows.

Source-code (zlib) can be found here, assets are licensed under the CC-by-NC-SA/ND. Build with the great Lua 2D game framework LÖVE by the way.

Read More

Dijkstra's Algorithm and reprioritizing nodes

I'm working on a tutorial showing how Breadth First Search, Dijkstra's Algorithm, Greedy Best-First Search, and A* are related. I'm focusing on keeping the code simple and easy to understand.

While tracking down a bug in my Dijkstra's Algorithm code, I realized I had forgotten to implement the "reprioritize" case. That led me to wonder why my code seemed to work without handling that case. It turns out that case is never triggered by the graphs I'm searching over. Let me explore this …

Algorithm textbooks describe the algorithm as starting with \(\infty\) everywhere and then checking the new cost against the old cost. The old cost is always defined so it's a single test:

if cost_so_far[current] + cost(current, next) < cost_so_far[next]:
    cost_so_far[next] = cost_so_far[current] + cost(current, next)
    came_from[next] = current
    frontier.reprioritize(next, cost_so_far[next])

In practice I don't initialize the priority queue to have all vertices with distance set to \(\infty\). Instead, I start the priority queue with only the start element, and only insert elements when their distance is finite. Keeping the priority queue small makes it significantly faster, especially with early exit.

However, this complicates the code. I now have two cases instead of one:

1. The new cost is less than the old cost because the old cost was \(\infty\), and we need to insert the node into the priority queue. This is a simpler operation, and it's more common, so it's worth separating out.
   


2. The node wasn't already in the priority queue, and has no old cost, and we need to reprioritize the node already in the priority queue. This is rare and more complicated than an insert.
   

This logic can go either in the algorithm code or in the priority queue code. I had put it in the algorithm (but in the tutorial I am going to instead put it in the priority queue, because it keeps the algorithm easier to understand).

if next not in cost_so_far:
    cost_so_far[next] = cost_so_far[current] + cost(current, next)
    came_from[next] = current
    frontier.insert(next, cost_so_far[next])
elif cost_so_far[current] + cost(current, next) < cost_so_far[next]:
    cost_so_far[next] = cost_so_far[current] + cost(current, next)
    came_from[next] = current
    frontier.reprioritize(next, cost_so_far[next])

I wanted to better understand which situations lead to the reprioritize case. Let's say we're looking at edge \(b \rightarrow c\) and we previously found \(c\) via edge \(a \rightarrow c\). (Note: algorithm textbooks call this \(g\) but I call it cost_so_far)

1. To trigger the reprioritize case, I need the old cost to be worse than the new cost: \( g(a) + \mathit{cost}(a,c) > g(b) + \mathit{cost}(b,c) \).
   


2. Dijkstra's Algorithm explores nodes in increasing order. Since \(a\) was explored before \(b\), \( g(a) \leq g(b) \), or equivalently, \( g(b) - g(a) \geq 0 \)
   

Those two together can be rewritten as \( \mathit{cost}(a,c) - \mathit{cost}(b,c) > g(b) - g(a) \geq 0 \)

That means when \(\mathit{cost}(a,c) - \mathit{cost}(b,c) > 0\) we need to reprioritize.

In several of my game projects, \(\mathit{cost}(x,y)\) depends only on \(y\). That means \(\mathit{cost}(a,c) = \mathit{cost}(b,c)\), and we never need to reprioritize.

That means any bugs in my reprioritize code never mattered!

It also means the abstraction boundaries between the graph data structure, the search algorithm, and the priority queue data structure potentially make the code more complicated and hurting optimization opportunities. I think this rule works, but I'm not sure: if we have a monotonic ordering (always with Dijkstra's algorithm, and A* with a consistent heuristic), and the movement cost only depends on the target node, then we never need to reprioritize. And that means we can use a simpler and faster regular priority queue instead of a reprioritizable priority queue.

Read More

DevCorner: GameDevelop goes open-source

Thanks to GamingOnLinux for pointing out that this crossplattform *no-programming* 2D game development suite has gone fully FOSS.
It can export games to HTML5 and native code (x86 Linux and Windows).

Read the original announcement here. The github repository is here.

License infos:

• The IDE (in the IDE folder) is licensed with GPL v3. 

• The Core library, the native and HTML5 platforms (respectively Core, GDCpp and GDJS folders) are LGPL v3. 

• Extensions (in the Extensions folder) are using zlib/libpng license. 

• The name, Game Develop, and its logo are the exclusive property of Florian Rival.

Here is a small video to get you started:


& you can find some example games here.
----
By the way: I also recommend to have another look at the Godot engine which has had many improvements since it became open-source a few months ago.

Read More

Winner of the Linux Game Awards PotM July 2014 announced!

See full announcement here.



Congrats to Unvanquished, they are doing a great job for sure!

While they won by a clear lead, the follow-up projects are also very much worth mentioning:

Read More