Tag Info

Hot answers tagged

25

In most cases, using A* over a navigation mesh (commonly referred to as a "navmesh") is the pathfinding solution commercial RTSs use. There is a detailed explanation of how navmeshes work, why they are a better solution than waypoint systems, and links to implementation resources, here. If you're planning on developing special game modes (point/node ...


21

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 ...


14

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 ...


12

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 ...


10

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 ...


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

I'm not very familiar with many of them but I have seen the usage of Dijkstra's algorithm not for pathfinding but for finding the nearest X to you. For example, what powerup is closest to you or what enemy is closest to you out of a group of enemies. So a "target nearest enemy" function often uses that.


4

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

Many older games do use A*. The original Starcraft used A*; which led to some problems in dealing with collision. Starcraft 2's handles collision very well, using a swaming/flocking behavior to maintain fluid control of large groups. This gamedev article discusses how this might be being achieve.


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). ...


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 ...


3

What you are really listing are, rather, graph search algorithms, which are a part of Graph Theory. A* happens to be one which is optimized for "pathfinding" applications. Why bother? Those algorithms are good for much, much more than simple pathfinding. In fact, there is an entire branch of mathematics devoted to studying graph theory and its ...


2

I agree upon the other answers her already, but also, try to think of WoW/Warcraft3 as actual 2D worlds. They arent that different from tilebased, its just the tiles. You could also think of how does a GPS find the best path? there a loads of algortimns for pathfinding through linked maps. I think some of the first "Quake bots" scripts also might help you, ...


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

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

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

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 ...


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. ( ...


1

Well, I don't think plants vs zombies has much in the way of path finding. Just moves left. You could just generate a random number from 1 to 5 or however many lanes you have and stick the enemy there. Maybe with the constraint that it can't roll the same number twice. Or if it does re roll so you don't get too many in the same lane


1

Search the non-ceiling edges for non-bubbles, and then check for non-bubble paths between these nodes. Example: ------------ 005163215101 205143122500 100064131001 215061356132 In this case, there is a path from the top-left corner (non-bubble touching the non-ceiling left wall) to the 4th spot on the bottom edge consisting entirely of non-bubbles. This ...


1

I think it would be easy to implement BFS or DFS to search same colors. You can just go to all of it's neighbours and then to their neighbours (if they are of the same color) etc. So you will create graph, where every point is connected to its four- (or eight-) neighborhood.


1

Map is a grid. Grid is a graph. A* works on graph, it is a graphs searching algorithm. A* should search few nodes of graph. As has been mentioned they can use navigation mesh. But the A* (or something similar) will be on top of that mesh anyway, because polygons of this mesh are just nodes of a graph; A* will then search for path from one polygon to another ...


1

I'm totally not experienced, but I think that a good solution is based on heuristics, not on a complete checking of the known map. Heuristics I can think of are locally based and experience based. Local controls can be based on local terrain check and obstacles, keeping moving toward the required direction. I think that most maps don't require complex ...


1

Most games do use some sort of Search Algorithm or A* to find paths on a map. The AI is tweaked in some aspects obviously for performance reasons. You will notice this in Starcraft 2 where Zerglings obviously don't path well at all, it would be a CPU nightmare to do that for Zerglings. They just do there best to get from A to B and don't even attempt to ...



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