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,168 questions
0
votes
1
answer
75
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 ...
- 45
0
votes
0
answers
59
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,411
0
votes
0
answers
79
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 ...
- 211
0
votes
2
answers
149
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,...
- 507
0
votes
0
answers
51
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 ...
3
votes
2
answers
115
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 ...
user70223
2
votes
2
answers
76
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 ...
- 211
2
votes
2
answers
177
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 ...
user183738
1
vote
1
answer
152
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
0
votes
0
answers
14
views
How to find offsets of Vector2's give number of points row, amount of points, and centered vertically?
Say that I want to make a grid that contains 5 points and up to 3 points on each row. starting from the top I should have 3 points followed by 2 points underneath centered by the same distance like so:...
- 1
0
votes
0
answers
81
views
What Algorithm to use for calculating a leaderboard
I would like to use an algorithm for an app where you calculate a leaderboard of people where they have played eachother a different number of times in a match.
For example , for a set week a group of ...
- 1
0
votes
0
answers
51
views
Obtaining randomGenerator's seed for Ender Crystal spike generation (pre-1.9)
I had an old world of mine that I wanted to re-create. I managed to obtain the world seed, so the Overworld and the Nether were ready, but the End not so much. Even though the island was generated ...
- 1
0
votes
0
answers
67
views
How to optimize random path generation with checkpoints and collision detection
I'm looking for a way to generate a random path based on midi note onsets (timing points) for a simulation/game.
I will briefly explain how it works for context:
I'm working on a simulation type game ...
- 1
1
vote
2
answers
228
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,055
0
votes
1
answer
85
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 ...
- 47
2
votes
2
answers
268
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
0
votes
2
answers
122
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 ...
- 103
1
vote
0
answers
122
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 ...
- 11
0
votes
2
answers
98
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 ...
- 211
0
votes
0
answers
71
views
How to efficiently hash canonized structs
Say I have a canonized struct:
{
health: 100,
items: ["apple", "knife"],
name: "Bobby"
}
"Canonized" here means ...
- 196
6
votes
4
answers
600
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
0
votes
1
answer
61
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 ...
2
votes
2
answers
216
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
0
votes
0
answers
82
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
146
views
Angry Birds style aiming (ballistic trajectory)
Could you please provide guidance on how to create the curved part?
regard,
0
votes
2
answers
135
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 ...
- 1
1
vote
1
answer
125
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 ...
- 113
0
votes
1
answer
82
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:
...
- 101
0
votes
0
answers
88
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'...
- 101
1
vote
0
answers
45
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
141
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 ...
2
votes
0
answers
66
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 ...
- 147
0
votes
0
answers
246
views
Generating tris for concave polygon 2D
I have an arbitrary array of points that describe vertices of the polygon 2D, they ar in order. To generate plane mesh for that, I need to generate tris. For something like circle/hexagon/square it is ...
- 1
1
vote
1
answer
162
views
Getting coordinates within a bezier space
I have created an object that is comprised of two bezier curves (constructed of an identical finite segments equal to a variable named resolution). The two curves ...
- 11
0
votes
2
answers
555
views
How to get area of 2D shape bounded by vertical and horizontal line segments?
I am making a game similar to Volfied using Unity:
The player outlines an area using straight lines, either horizontal or vertical.
I am stuck at the algorithm to decompose the area into rectangles ...
- 101
4
votes
1
answer
541
views
Find a encircliement in Hexagonal grid (optimization issue)
I have a hex grid of 10000 cells (100x100). The player can grab a cell next to one of his cells (borders). If the player has formed a ring after placing a cell, I want to get a list of cells that ...
0
votes
1
answer
294
views
How can I simulate lamp flicker in a Unity shader?
I want a game object to keep its brightness (modulating mainColor, like mainColor * brightness) most of the time, but sometimes ...
- 263
1
vote
2
answers
307
views
Why is my negamax algorithm returning negative infinity scores?
I'm currently in the process of writing my own chess engine in java and am having a little trouble with negamax. I've opted for negamax since its easier on the eyes and reduces the number of lines of ...
- 11
1
vote
1
answer
558
views
Find possible paths in a grid
I want to make a simple maze with colour-coded cells:
white denotes a blank space,
black denotes a wall,
green denotes source and
red denotes destination.
So, my idea was to write an array of ...
- 157
2
votes
0
answers
573
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 ...
- 73
0
votes
1
answer
436
views
How do you resolve continuous collision in a multi body system?
I've been trying to figure this out for weeks but every resource only provides answers for a single body. As far as I can tell for a single body you
Find the time of impact
Step up to that time
...
- 1
0
votes
1
answer
40
views
Make linear parameter change seem chaotic
I'm trying to solve a challenge with linearity of my animation. Let say we have a Tug of war mechanic. One team is much stronger and it moves line from point A(0) to point B(10) with a speed of 1 unit ...
- 29
1
vote
4
answers
249
views
How to increase difficulty of a catching game
I'm developing a game where products fall from the sky, and you need to catch them. A bomb also falls, and if you catch it, you die.
I have 3 different products with 3 different scores.
I want the ...
- 11
0
votes
1
answer
251
views
Implementing a bot to find the player in a grid
I have a 2d array with ground represented by 0s and the walls represented by 1s.
Player can use a LOOK command or a MOVE command. Look command returns a 5x5 array centered around the player and the ...
0
votes
0
answers
512
views
How to implement Glicko-2 rating system in a scalable way?
I have a multiplayer game that, similar to chess, will have a win/tie/lose outcome in a 1v1 setting.
I've been looking at Elo versus Glicko & Glicko-2 and it seems Glicko-2 might be a good one to ...
- 111
1
vote
1
answer
135
views
Randomly distribute damage among allies
Let's say I have regiments of varying sizes, 500, 1000, 4000 troops.
I want to distribute 1000 troops worth of losses to them so that in aggregate they lose 1000 troops. I want to do it as a ...
- 167
0
votes
2
answers
317
views
Numbering sprites in a sprite sheet left-to-right, top-to-bottom
I'm using this program called Quadtastic which is a sprite sheet management tool that lets you define quads on a sprite sheet, name them, etc, and export to metadata with those names (+ position, size,...
- 1,075
0
votes
0
answers
54
views
Wheel position on surface
I have a bicycle with suspension and need to find the contact point of the wheel on the "road". If the front fork was pointing straight down, it would be as easy as doing a raycast down the ...
- 77
0
votes
1
answer
255
views
Scaling Weighted Loot Table
I'm working on an astroid mining game where there's the player controlled ship that can split astroids into smaller ore chunks to then collect and bring back to a base station for processing. I'd like ...
1
vote
0
answers
43
views
How to limit the character movements to a delimited area
Consider the below images get from the Final Fantasy VII and Alone In The Dark games:
I assume that the above scenes are composed by a set of layers composing the background image (allowing thus the ...
