Questions tagged [search]
The search tag has no usage guidance.
29 questions
56
votes
5
answers
8k
views
How could I implement something like Minecraft's crafting grid?
The crafting system in Minecraft uses a 2x2 or 3x3 grid. You place ingredients on the grid, and if you put the right ingredients in the right pattern, it will activate the recipe.
Some interesting ...
- 713
47
votes
9
answers
35k
views
How does pathfinding in RTS games work?
[crossposted from stackoverflow]
In a game such as Warcraft 3 or Age of Empires, the ways that an AI opponent can move about the map seem almost limitless. The maps are huge and the position of other ...
- 471
6
votes
4
answers
3k
views
Is there a known most efficient version of A* search algorithm?
Is there a known 'most efficient' version of the A* search algorithm? I know some people write papers on the most efficient way to compute common operations, has this been done for A*?
- 3,450
6
votes
2
answers
5k
views
Bubble shooter search alghoritm
So I have a Matrix of NxM. At a given position (for ex. [2][5]) I have a value which represents a color. If there is nothing at that point the value is -1. What I need to do is after I add a new point,...
- 469
5
votes
1
answer
3k
views
Find sub-graphs in a graph
The initial problem I'm trying to solve is for pac-man, but of course there must be thousands of other situations with the same problem. I consider the pac-man grid to be a graph (two ways of doing ...
- 233
5
votes
1
answer
793
views
Verify which bubble is connected to top using DFS
I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine.
Update
Here is my ...
- 61
4
votes
3
answers
5k
views
Bubble shooter falling algorithm
To complete this question about the same color search algorithm, I would like to know if someone knows which is the best implementation for making other bubbles fall when they are no longer attached. ...
- 143
4
votes
1
answer
192
views
Best approach to get clicked objects from a display list (2D)
I'm implementing a display list to manage my visuals on screen.
I want to know which object is clicked.
My objects already have z-order variable.
With my current knowledge (almost nothing) the only ...
- 153
3
votes
6
answers
2k
views
In what instances would you want to use path-finding algorithms other than A*?
I am familiar with how the common ones technically work (BFS, DFS, Dijkstra, A*) but as far as their realistic benefits I don't quite see the need for them. Considering that, given the right ...
- 587
3
votes
1
answer
605
views
Finding break in voxel grid (3D array)
I am working at dynamic voxel engine in Unity (something like Space Engineers) where player can create object from voxels, push them, damage and split in to other object.
I store all data in 3D array,...
2
votes
2
answers
2k
views
Is any data structure more efficient than quad-tree for storing and querying points that lay within an OBB?
Is there any method more effective than quad-trees for storing and searching sets of points that are not spread uniformly on the plane?
I need to be able to add, remove and search for points that are ...
- 10.5k
2
votes
1
answer
975
views
Finding flexible patterns in a 2D grid
I'm stumped trying to create a matching algorithm for my game.
I have a 2D grid like this for example:
0, 0, 0, 0, 0, 0
0, 1, 2, 2, 1, 0
0, 1, 1, 0, 0, 0
0, 0, 2, 0, 1, 0
0, 0, 0, 2, 1, 0
0, 0, ...
- 165
2
votes
0
answers
2k
views
Z-order curve — how to query all nearest neighbors?
TLDR: How to query all nearest neighbors with the least effort? (Iterating over a bigger neighboring area that's continuous and filtering out elements that are not immediate neighbors?)
Suppose the ...
- 121
1
vote
3
answers
4k
views
What are the most common AI systems implemented in Tower Defense Games
I'm currently in the middle of researching on the various types of AI techniques used in tower defense type games. If someone could be help me in understanding the different types of techniques and ...
- 133
1
vote
2
answers
259
views
How could a NPC find items that appear randomly?
My main question is basically: What is the algorithm that CPU players use in smash bros to find items like the smash ball? I am trying to make a small ai character that will "look around" and once an ...
- 113
1
vote
2
answers
973
views
Efficient fog-of-war visibility searching
Every game I look into that uses fog of war tends to have the AI ignore fog of war completely. I'm starting to see why.
I have a RTS game I'm working on, with lots of units moving around. All units ...
- 614
1
vote
1
answer
1k
views
Scanning a 2D tile map and detecting regions?
I have access to all points/tiles on the map with top-right most point being (0,0). Simplest way to traverse the map would be using for loops, one nested within the other to traverse the x axis, and ...
- 111
1
vote
2
answers
196
views
What graph Search algorithm (s) that can simulate the behaviour of a human searching in a forest
We are building a game , where a group of humans(AI agents) have to wander seperatly throughout the forest looking for a collectable item.
The forest is represented as a 2d graph with the item ...
- 111
1
vote
2
answers
2k
views
Implementing an AI controller for Pacman
I'm currently implementing an AI controller class that is being used to determine the moves that ms.pacman should make to collect pills and avoid ghosts. In order to determine which is the best move ...
- 241
1
vote
0
answers
395
views
Overlap detection, nearest neighbors
I'm trying to get something similar to the Nearest Neightbor Problem, except I only want neighbors with radius overlapping a radius, and all of them.
I'll explain my problem before explaining what I ...
- 322
0
votes
2
answers
325
views
Job finding algorithm
My issue seems simple enough to me, but I can't break it down the the bare essentials to be able to program it into my game.
First of all different professions requires different skills, these skills ...
- 11
0
votes
1
answer
173
views
What could I use to search tiles in a game [duplicate]
I'm creating a tile based game similar to Minesweeper. When a user clicks on a tile and its not a mine or a number space I need to search and expose the adjacent tiles that are empty and stop when it ...
- 369
0
votes
1
answer
129
views
What algorithm is best for finding non-static nearest neighbors on a 2d grid?
A bottleneck I've hit is querying Quadtrees for finding nearby locations. It's much faster than comparing each location, but I'd like to find faster methods that work for moving locations. Profiles ...
0
votes
1
answer
71
views
How to make an expanding radial search in Unity?
I am currently working on a City Builder Game and I often come across the problem of having to decide wich location to use.
Examples:
The citizen has a job and needs a home. There are several ...
- 99
0
votes
1
answer
58
views
App Store Optimisation-Package Name
I have a game in play store and trying to get it to the upper places on the search engine. As I read, the package name should be similar to the game title. What is the effect of it in the searches?
I ...
0
votes
1
answer
151
views
A* Implementation broken?
I tried implementing Wikipedia's version of the A* pathfinding algorithm, but when I run it in Unity the object which the script is applied to does nothing and Unity ends up taking 15% of my CPU. I ...
- 21
0
votes
0
answers
160
views
Minimax implementation problem
it's my first time posting so apologies in advance if the format is weird. I'm developing a board game that's very similar to checkers/chess and I've faced some problems implementing the minimax/...
- 1
0
votes
1
answer
1k
views
Why do KD trees put the median split exactly on a point?
I've understood that KD tree split points using the median while cycling on each axis. I've also understood that at each node traversal, a nearest search must use a sphere to store to nearest neighbor ...
- 5,253
-2
votes
2
answers
2k
views
Tower Defense Search Enemies Efficiently
I had a problem with the build of a TD.
I got a slow - non efficient search for towers find targets to shoot.
PD: enemies[] got all the active & non-active enemies (death and alive) ->Im using ...
- 9