Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Hot answers tagged

23

You have to remember that Minecraft only uses a very small set of possible recipes, so there is no need for anything all that smart. That said what I would do is find the smallest grid that fits (i.e. ignore empty rows and columns to find out if it's a 2x2 or 3x3, or 2x3 (door)). Then loop through the list of recipes with that size, simply checking whether ...


15

If you don't mind bibliography, take this list as a starting point. It's a series of articles from the Game Programming Gems and the AI Game Programming Wisdom series, with the most relevant ones being: Beyond A* - Game Programming Gems 5 Advanced Pathfinding with Minimal Replanning Cost: Dynamic A Star (D*) - Game Programming Gems 5 How to Achieve ...


15

Seeing if a certain grid configuration matches a certain recipe is simple if you encode the 3x3 grid as a string and use a regular expression match. Speeding up the look up is a different matter, which I'll talk about in the end. Read on for more information. Step 1) Encode grid as String Simply give a char id to each type of cell and concatenate ...


14

Another solution is to use a somewhat complicated tree. The branch nodes in your tree would be created by iterating over the recipe (once again using for (y) { for (x) }); this is your stock-standard by-the-book tree structure. Your final node would contain an additional structure (Dictionary/HashMap) that maps dimensions to recipes. Essentially what you ...


7

What you need here is a depth first search. int R, C; int[][] matrix; int count; boolean[][] visited; int NOCOLOR = -1; public int main() { int startR = 0; int startC = 0; int color = 1 // red int R = 10; int C = 20; matrix = new int[R][C]; visited = new boolean[R][C]; matrix = LoadLevel(); // get a starting ...


5

Keeping things simple I don't know the exact context of your problem, but I give below the most accurate solution possible given the specific question you've asked. However, if you want to keep things simple, it is better to construct the graph yourself. In that way, there is no need for you to identify subgraphs, since in creating them within a larger ...


4

You're on the right track. The thing you're looking for is a space partitioning data structure. For a 2D system I'd go ether with a quadtree (if object sizes vary a lot) or a simple grid (if object sizes are similar). I've already written two answers on the subject, so instead of repeating myself I'll just link you to them: How to continuously find all ...


4

A* will work, but for a Tower Defense game that has lots of enemies with the same goal and a relatively static geometry, it may actually be cheaper to just run Dijkstra's algorithm backwards from the goal, to find the shortest path tree from anywhere on the map to the goal, and cache the result until the geometry changes (i.e. a tower is built or destroyed). ...


4

D* Lite if you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, and which can adapt to a changing map. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been ...


4

Bit of an old one (stumbled into this searching for something else entirely) but I didn't see Jump Point Search explicitly mentioned. There's a good article here (which I think is from someone who worked closely on the development of the approach) that describes very well how it works, how to implement it, and why it's faster. Briefly it works on the ...


3

You might want to give R-trees a try. They are similar to quad-trees in that they subdivide the plane recursively; however, unlike quad-trees, they do not necessarily split up each sub-plane into equally sized, non-overlapping quarters. Instead, sub-partitions are flexible in position and size. From wikipedia: The key idea of the data structure is to ...


3

When you remove a node, take any solid nodes attached to it and do a connectivity test between each pair. If any of the solid nodes that were once connected to the solid node you just removed are no longer connected, then removing that node has just created two separate objects. This algorithm isn't affected by the size of the grid, but rather the size of ...


3

Inefficient is fine if it's not using much cpu relative to other parts of your game. :) Start with the simple implementation and then go back and improve it later, only if needed. Your pseudocode uses a queue but you don't really need the entire queue; you only need the max. If you have lots of workers and lots of buildings, with your algorithm you may end ...


3

I can't tell you how the Minecraft one works - although I am sure if you looked at MCP (if you have a legal copy of Minecraft) you could find out. I would implement this as follows: Have some disk-based dictionary/hashmap (B+Tree/SQL-Light) - the value would be the item ID of the recipe result. When a user is crafting something simply find the first row/...


3

If you're working with a uniform-weighted grid and don't need to worry about dynamic pathing, Jump-Point Search is an extremely efficient pathfinding algorithm. It's extremely fast, usually ten-to-thirty times as speedy as A*. It achieves this through symmetry reduction, which is a method by which empty spaces are ignored.


3

On spawn of the object, relevant "listeners" (your NPCs) should be pinged. Once pinged, the listener can now use the distance from the object, line of sight of the object, the value of the object, the distance of other interested listeners from the object, and other useful variables to develop a weight or a metric that would prioritize any number of ...


2

A* is the basic, most widely used, most general purpose graph traversal algorithm. Given a set of nodes, edges, and weights for those edges, a starting node, and an ending node, A* will find the shortest path between the 2 points. As you must know, many variants on A* exist. Some of these variants do things like allow for edge weights to change (...


2

Here is how I did it in Block Story:


2

Every bubble that isn't floating must have some path going back to a top bubble (are we assuming the side walls aren't "glue"?). Apply a flood fill algorithm for every bubble found in the top row. Doing this for every top bubble is essential because it'll work flawlessly in any case, in particular if there are several columns of bubbles hanging from the top ...


2

One simple method would be to write a function that starts at a bubble touching the top wall and runs through all it's neighbors (and recursively their neighbors with a method to prevent going to ones that have already been visited) then check to see any that didn't get visited by the function call. Any that didn't aren't attached to anything and therefor ...


2

A naive algorithm to find one pattern in a grid would be this: for (int grid_x = 0; grid_x < grid_width; grid_x++) { for (int grid_y = 0; grid_y < grid_height; grid_y++) { bool fail = false; for (pattern_x = 0; pattern_x < pattern_width && fail == false; pattern_x++) { for (pattern_y = 0; pattern_y < ...


2

You might also want to take a look in other algorithms described in maximum weighted matching in bi-partite graphs. In your case, all the people looking for the job should be placed in same group, and all the jobs should be placed in the other. Obviously there is no edge between vertices in the same group, and for person-job edge, it's weight would be equal ...


2

The search algorithm you're looking for is called Flood Fill Every empty tile is colour A. Every non-empty tile is colour B. Then you apply the flood fill with the modification that you also stop filling in that direction when there's an adjacent non-empty tile. Alternatively: every empty-with-no-adjacent-non-empty tile is colour A, all the others colour B,...


1

Keep the array free of dead creatures. Here is the API for manipulating arrays. See removeObjectAtIndex You can iterate once over all living creatures and check if their distance from each tower is smaller than the range of the tower. If so decide on the factor you wish to pick the target by. Normally towers pick the target that is closest to the objective. ...


1

The two options I see are to record per-player visibility flags within the grid points themselves, and then (somehow) update those flags each frame... This seems like the right answer to me. Store whether or not each player can see each grid point. Updating the map can actually be very simple and efficient. You presumably already update each unit. When you ...


1

I think, that's work for influence maps. It's almost your first option but in more common interpretation for AI in games. Influence maps presents all your map with grid in some specific structure. For each cell you save some value and periodically update it. In your case, you can save last_seen_time as value. So, when you'll iterate scrap to find new target, ...


1

Another similar and useful data structure is the kd-tree. It divides the k dimensional space by spiting it recursively much like an R-tree. Some differences are described here: https://stackoverflow.com/questions/4326332/could-anyone-tell-me-whats-the-difference-between-kd-tree-and-r-tree An important difference is that some say kd-trees are hard to ...


1

If you are using DFS starting from the top, all unvisited nodes should drop. The top should be an invisible node connected to all top bubbles (in the top row). One thing worth noting, is that unlike the current DFS which is checking for color equality, the functionality you should use for deciding which bubbles to drop because they are hanging in the air ...


1

If someone could be help me in understanding the different types of techniques and their associated advantages. I want to answer that question by listing three techniques I would use if I were to implement a TD game: 1) Finite state machines or behavior trees for the little AI any agent would need. For something as simple as TD I'd probably use FSM. ( 2) ...


Only top voted, non community-wiki answers of a minimum length are eligible