3,483 reputation
720
bio website redblobgames.com
location California
age
visits member for 4 years, 6 months
seen 16 hours ago

I help people make games. On my new site ("Red Blob Games") I post interactive tutorials and guides to game algorithms. On my previous site (Amit's Game Programming Information) I collect links to useful pages about maps, grids, tiles, pathfinding, and AI. On my blog ("Blobs in Games") I post experiments and projects and ideas. Previously I was an advisor to Wild Shadow Studios (Realm of the Mad God) and Root 1 (educational games).


Apr
9
awarded  Nice Answer
Mar
20
comment A* pathfinding for grid with direction-dependent nodes?
Yes. A* considers whether you can move from A to B separately from whether you can move from B to A. You can have one or the other or both or neither. It also considers the cost of moving from A to B separately from the cost of moving from B to A, so climbing up could be slower than climbing down.
Mar
14
comment How to select random points within grid meeting min/max distance requirements from each other?
I'm guessing poisson discs will be useful for this. You can use a quad tree or sorted range data structure to help find the closest point to your new proposed point. Jason Davies has a demo of an efficient algorithm but it only handles M and not your L condition. Still might be a good starting point.
Mar
7
answered Estimate the time it takes for an object to travel from point A to point B
Mar
1
answered Finding neighboring coordinates on offset tile map
Feb
21
answered How to get more gentle (cloud like) noise?
Feb
17
comment Optimization of A* in Python
200 000 times per second is quite unusual. Can you describe more what you are trying to do here?
Feb
16
awarded  Revival
Feb
15
answered How to find all the possible places to go on a grid?
Feb
14
comment How can I use graph traversal to generate a round region?
CA doesn't start from a root node and expand; it evaluates all nodes equally. You may be thinking of graph traversal algorithms.
Feb
11
comment Possible A* Optimizations
@PieterGeerkens The same node can occur in the neighbors list of many other nodes. A* usually checks if the node is already in the Open set. If it's already there, and the previous 'g' value is lower (better) or equal then you don't need to insert the new node. If it's already there, and the previous 'g' value is higher (worse) then you should put the new node into the priority queue. Some implementations will update the existing node in the priority queue to reduce the number of nodes it has (speeding up the PQ) and to reduce the number of nodes processed (speeding up A*).
Feb
11
comment Possible A* Optimizations
Does the profiler tell you which lines are slowest?
Feb
9
comment How can I use graph traversal to generate a round region?
I'm curious — why do you want to use cellular automata for this?
Feb
4
comment Backtracking in A Star
The open list is not where you are actually moving. It is where you are considering moving. A human is able to "jump around" when considering possible moves, and A* does that too. If you really want to backtrack then consider the Depth First Search algorithm instead of A*.
Jan
28
awarded  Talkative
Jan
28
answered Simplify paths when a user builds
Jan
4
answered Storing walls that are between tiles
Dec
14
comment Tetris rotation without using arrays
You should use whatever's easiest. This doesn't seem like it's worth optimizing, unless the profiler tells you you're spending a lot of time there. O(n^2) hardly matters when n is 4.
Nov
29
answered Why is 2D light ray collision result getting inverted at specyfic angle
Nov
17
comment How to draw the contour of a hexagon area, like in Civ 5
If you really need to build polylines, each edge endpoint is connected to two more edges. Only one of those two edges is the one you need to follow. There is a hex to your left, a hex to your right, and a hex in front of you. If the hex in front matches the one to the left, you need to follow the edge to the right; otherwise follow the edge to the left.