Questions tagged [algorithm]
Algorithms are used for calculation, data processing, and automated reasoning. More precisely, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function.
1,167 questions
0
votes
1
answer
64
views
Is an assumption of Welzl’s algorithm valid?
The stated assertion that a point outside some intermediate Minimum Enclosing Sphere is on the boundary of the final Minimum Enclosing Sphere seems unsupportable. It is true only for the first point ...
- 141k
4
votes
1
answer
152
views
How would I find the best set of letters for my word game?
I'm making a game where players need to spell English words (including American and British English) using a limited set of 8 distinct letters, which can be re-used multiple times.
How would I go ...
- 141k
0
votes
1
answer
2k
views
In Unity, how can I render borders of provinces from a colored province map in a grand strategy game?
I am kind of a beginner of Unity and I am trying do work on a grand strategy game. I already have a province map, colored by unique rgba for each province, looks like something below:
I know that the ...
CommunityBot
- 1
2
votes
2
answers
12k
views
How does HPA*(Hierarchical Pathfinding A*) really work?
I'm currently researching, for a summary paper, the different variants of A* search algorithm and how they are used in games.
I stumbled across the name HPA*. I've heard that it's much faster than ...
- 3
13
votes
3
answers
880
views
Gesture Recognition Strategies
Working with the Wii I often find it necessary to recognize simple gestures, so far I've been able to mainly look at magnitude of acceleration in order to recognize the gestures called out for in our ...
4
votes
1
answer
241
views
Train simulator - approach to cars movement
I'm prototyping a train simulator and running into design issues with physics and train car movement. The scope is similar to games like Run8, SimRail, or Derail Valley.
Requirements:
Realistic train ...
- 853
8
votes
2
answers
2k
views
Help understanding Simplex Noise
Introduction
This is less of a "how to" on using 2D simplex noise and more of a quest to understand what is happening both in the math and visually. I would rather not copy and paste the code I've ...
- 111
0
votes
1
answer
131
views
How to calculate the border hexagons in a grid with blocking elements?
I have a hexagon grid with cubic coordinates. I want to calculate clockwise all border hexagons for a given movement range. At the moment, I am iterating every neighbor that is not in the range and is ...
- 141k
0
votes
0
answers
76
views
How to optimally transfer between nodes when each connection can only handle a certain number of things at a time?
Let's begin with a picture:
I am currently making a turn-based strategy game set in space where you can settle colonies and have to transfer minerals from the colonies ("foo", "bar&...
- 8,543
0
votes
0
answers
124
views
Strategies for making NPCs respond to player queries based on the NPC's knowledge or activity
I'm developing a finite state machine AI where some interaction with the NPC can be made through a popup window with some choices. The image below shows how it looks:
The player (on the right in this ...
- 141k
3
votes
2
answers
189
views
How to make a digger-like procedurally generated maze that can be queried at coordinates without having to generate?
I would like to procedurally-generate ant farm-style layouts on a grid: long horizontal spaces connected by short vertical spaces. Also similar to cave systems formed by water erosion.
Every tile in ...
- 141k
18
votes
1
answer
5k
views
Algorithm for "healing" multiple rectangles into a smaller number of rectangles?
Say I have a grid of rectangles of different shapes and colors and I want to reduce (reasonably close to optimal is fine, optimal is not necessary) the number of rectangles to represent the same ...
- 141k
2
votes
2
answers
134
views
Improving local collision avoidance to navigate around large obstacles
For my collision system I’m using a boids-like method that works fine for "small" obstacles (like other characters) where the character can turn slightly left or right to avoid the obstacle ...
- 333
0
votes
1
answer
230
views
Coding a customizable JRPG random action system in Godot 4? [duplicate]
I'm making an open source turn based JRPG in Godot 4.3, I want any programmer to be able to very easily create new enemies with different behaviors by simply customizing export variables in the editor,...
- 853
6
votes
2
answers
2k
views
Repairing back-facing triangles without user input
My 3D application works with user-imported 3D models.
Frequently, those models have a few vertices facing into the wrong direction. (For example, there is a 3D roof and a few triangles of that roof ...
- 3,141
0
votes
0
answers
88
views
How can the A* algorithm revisit the same node twice in multi-agent pathfinding(MAPF)?
I am attempting to solve a MAPF-like problem using the Conflict-Based Search (CBS) algorithm. My specific problem is based on a grid graph where some edges are not connected.
For example, in the ...
0
votes
1
answer
190
views
how to order entities by their distance from 0 on the x axis
I'm creating an infinite runner game in which you control several characters at once. Right now when you press the spacebar, they all jump at once but, I want them to jump at separately, one after ...
- 522
2
votes
2
answers
259
views
Is using values from a cryptographic hash function for Perlin/Simplex noise innapropriate?
The permutation maps are usually the numbers from 0 to 255 arranged in a random order. If I were to use a cryptographic hash function to convert a string, and then use the result's individual integers ...
- 522
0
votes
2
answers
282
views
Can GJK be used with the same "direction finding method" every time?
In my deliberations on GJK (after watching http://mollyrocket.com/849) I came up with the idea that it ins not neccessary to use different methods for getting the new direction in the doSimplex ...
- 123
6
votes
1
answer
5k
views
Sweep and prune vs quad tree when all objects are dynamic (moving)
As I understand it there are 3 popular strategies for spatial partitioning: sweep and prune, quad/oct tree and uniform grid. Uniform grid is problematic for me because I have not set an upper limit on ...
- 103
1
vote
1
answer
247
views
Octree Query - Frustum Search and Recursive Vector Inserts
Brief
I have spent probably the last year thinking about implementing an Octree data structure into my C++ game engine project for scene management and frustum culling of lights and meshes. Right now ...
- 51
2
votes
2
answers
569
views
How to implement D&D 4e's line of sight algorithm?
D&D 4th Edition (the tabletop game) has combat on a 2D map with square tiles. A creature occupies an entire single tile.
The attacker has clear sight on the defender if lines can be drawn from ...
- 780
9
votes
3
answers
19k
views
How to decompose sprite sheet
I have a lot of spritesheets that are poorly formatted that I want to decompose, or split out into many small images, one for each sprite.
If I can do that, I can use my custom texture packer tool to ...
- 61
1
vote
2
answers
380
views
A*, what to do about duplicate items in the min-heap, if anything?
I'm trying to implement A*.
I'm storing the queue of nodes to visit in a min-heap, and I'm seeing the same node being added more than once to it (with different priority). Wikipedia's pseudocode ...
- 2,054
0
votes
1
answer
140
views
What are some basic methods/algorithms for drawing wireframe shapes using Gizmos?
This is definitely a "doing for the sake of learning" question, so apologies in advance for that, but how would you go about using the Gizmos class to draw a basic wireframe shape?
I'm ...
- 6,976
2
votes
2
answers
403
views
How would you intentionally create overlapping rooms with procedural generation?
It seems like every procedural dungeon generation tutorial focuses on how to avoid overlapping rooms, so how would one go about intentionally overlapping those rooms instead, possibly treating the ...
- 47
2
votes
0
answers
682
views
How can I add fake erosion in my infinite terrain generation?
I'm making a game where the terrain is infinite and procedurally generated. I'm using Perlin noise with octaves to make the terrain shape. I would like to implement some sort of erosion to make the ...
- 1
0
votes
2
answers
156
views
Using the boids algorithm for multidirectional boids
I have some difficulties with my basic collision system in croweded places as it is based on simple box to box or radius detection. Sometimes characters are stuck to something or stopped because there ...
- 333
0
votes
2
answers
164
views
How should I implement a terrain raise/lower brush? [closed]
I am trying to make an terrain editor. The terrain is described by a grayscale height map.
When I click at somewhere in the terrain map with the brush, the terrain should raise or lower about that ...
- 141k
0
votes
1
answer
415
views
Instantiate prefabs at particular vectors using text file
I need to read a text file containing two pieces of information on each line, and use that information to instantiate a prefab at the correct location in a Unity game (using a C# script). The ...
- 141k
1
vote
0
answers
216
views
Dynamically generating the layout of a skill tree
How would I go about automatically generating the layout of a skill tree?
Skill tree nodes have at least one parent, but they can have more. Ideally I'd have a root node that recursively creates its ...
- 10.7k
0
votes
0
answers
105
views
How to efficiently hash canonized structs
Say I have a canonized struct:
{
health: 100,
items: ["apple", "knife"],
name: "Bobby"
}
"Canonized" here means ...
- 196
0
votes
1
answer
103
views
I'm trying to find a way to iterate through a list of game objects to find furthest object in the list. Then re iterate if path is blocked
I've got the first part of the code working. It iterates and does a check through the gameobjects to find the furthest nav point to hit. Then it calculates path to see if its valid or not. Now I'm ...
- 141k
2
votes
2
answers
280
views
Identify doorways to partition a collection of walls with gaps into rooms
I am looking for an algorithm that can find separate rooms inside a set of walls, by determining which openings should be considered doorways between adjacent rooms. All is defined on a grid. My main ...
- 21
11
votes
1
answer
2k
views
Algorithm for constructing the corners of a regular, n-sided polygon
I've googled this using a lot of keyword combinations, but to my great surprise I could not find an algorithm for constructing a regular, n-sided polygon into a given circle, i.e., finding the ...
6
votes
4
answers
728
views
In a tile based game, with units that can move a specific amount per turn, how do i make my pathfinding avoid damage unless it is the only valid path?
i am making a 3d tactics game, visually similar to something like final fantasy tactics. it's tile based, with units able to move up and down the level onto buildings and up staircases and what have ...
- 65
62
votes
9
answers
58k
views
Texture packing algorithm
What is a good texture packing algorithm? Technically, bin packing is NP-hard, so a heuristic is what I'm really after.
- 141k
0
votes
0
answers
110
views
Find the best attack position
I'm doing what this thread is doing except that it's not very satisfactory. What this does is finding the "closest" attacking position. But typically you want the attacker to attack from as ...
-1
votes
1
answer
208
views
Angry Birds style aiming (ballistic trajectory)
Could you please provide guidance on how to create the curved part?
regard,
- 61
5
votes
3
answers
302
views
Determining a sensible gear-like hierarchy for a series of connected objects
I would like a series of objects to behave in similar manner to a series of connected gears.
This means that each black object in the diagram below will rotate at a speed based on the ratio of their ...
- 13.4k
0
votes
2
answers
233
views
How to compute XP thresholds when scaling changes for each level range?
I am developing mobile game and I am stuck on an issue regarding proper player stats scaling based on level.
As a parameters for the computation we have:
base XP value
multiple increment values (for ...
- 522
1
vote
1
answer
169
views
How to properly split damage against armor?
I am developing a third-person shooting style game and I want to implement an armor system. The system that I have envisioned does not reduce the damage to 0, but by half. So the incoming damage is ...
- 13.4k
0
votes
1
answer
114
views
Getting the scalar speed from an X and Y velocity [duplicate]
Given a Vector2(x,y) that represents an object's velocity, like so:
...
- 141k
7
votes
1
answer
1k
views
How can I create a six sided tillable perlin noise image?
I'm attempting to create a tillable hex shaped terrain map using c++.
As part of the process I'd like to use perlin noise, but it seems that in order to make it tillable I'll need to generate it 5 ...
- 141k
0
votes
3
answers
4k
views
How to move in 3D space in first person mode?
I have a Camera with Vector3 and also the camera has an angle.
If I use this:
hero.position.x += speedX;
hero.position.z += speedZ;
works great but as soon as I ...
- 10.7k
0
votes
0
answers
153
views
How to turn adjacent squares on a grid into larger rectangles? [duplicate]
I want to know what's the best way to combine individual squares on a grid (tilemap) into larger rectangles. I need this to simplify my physics collision detection/resolution, so that collision doesn'...
- 141k
3
votes
1
answer
3k
views
How can I morph between images in real time?
So, I need to be able to make a picture slowly transition into another picture, not as a transparency fade, but as a morph.
And I need that in real time.
More on "morphs":
When you outline ...
- 1
1
vote
0
answers
54
views
How to quickly traverse bi-directional nodes without repetition?
I want to optimize a bidirectional node traversal algorithm.
Because the node is bidirectional, it may cause an infinite loop. The current algorithm uses memory records.
However, memory writing will ...
- 41
0
votes
1
answer
171
views
Validate structure for a room escape game
In a game like a simple adventure or a room escape game, I would like to know if there are established algorithms to check for simple constraints on the layout.
I would like some pointers so I could ...
- 13.4k
2
votes
0
answers
89
views
Generate coastal line from water tiles
I have a 2D tiles map. Some tiles are water (black tiles on image). I can compute which tiles are coastal when it's 4 neighbors are not water (black dots on image).
I would like to compute coastal ...
- 159