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,094
questions
0
votes
1answer
30 views
Check if a procedurally generated maze built out of cubes is solvable
I have created a procedural level generator in unity.
However, occasionally the algorithm creates a level that is impossible to solve.
Therefore, I tried to implement a navmesh agent to check if it is ...
2
votes
1answer
74 views
How can I build an accurate 15-bit Highcolor RGB palette
I want to recreate an accurate version of a 15-bit RGB color palette (PC Highcolor, SNES, Playstation 1), storing each color from the palette as a standard 6 digit hex code.
With each color component ...
2
votes
3answers
629 views
How to read a sparse Octree sequentially, like a 3D array?
Is it possible to read a sparse Octree like a regular 3D grid:
for(z)
for(y)
for(x)
...and still benefit from skipping large empty areas?
I need this for a ...
0
votes
1answer
81 views
Confirming whether a user has drawn a character correctly
This is a follow-up post to this post: How can I check if a player-drawn line follows a path?. I'm having difficulty implementing the said feature and I believe it's because of a lack of math ...
1
vote
1answer
34 views
How can I remove unnecessary vertices from wall edges?
I've got a pretty simple tile based 2d top-down map with an array of walls. In order to figure where to cast light and shadows, I've generated an array of vertex coordinates along the walls like so:
...
1
vote
1answer
53 views
How to draw splatter (one color) on 2D grid to cover approximate number of pixels? (looking for algorithm/math answers)
Imagine a 2D grid, where water stain increasing because of water drops. But not in plain circular way but more like noisy-splatter way. Or like corruption way. I want to create effect that will ...
0
votes
1answer
29 views
1
vote
0answers
24 views
How to implement a big audio source and a cluster of audio sources?
I have a 3D game. The sound engine supports:
playing ambient music to the player (two channels always the same)
playing static sounds from a single position in space
playing mobile sounds from a ...
1
vote
1answer
81 views
How does a game like slither.io handle collision?
This question can be generalized to "how does one efficiently determine if a collision has taken place between curvy lines"
On https://slither.io there are snakes that players play as that ...
1
vote
1answer
59 views
How do I create an event trigger system for a Discord bot?
I am making a card game and I am having issues implementing "effects" and effects that are continuous.
How can I get effects to activate at the right times, before and after an attack does ...
0
votes
1answer
49 views
Recycling bullets versus spawning them on demand
Until now, I know 2 bullets' algorithms/configurations : (I mean 2 ways of logically creating a bullet class)
Make a bullet class and create only one instance from it that represents the bullet.
The ...
1
vote
1answer
46 views
Making Sprite Movement Appear More Natural
Currently I have a 2D game in which the player and a computer controlled (non-player) sprite move from point to point collecting tokens in a continuous environment. The player and the non-player ...
2
votes
1answer
48 views
Space out units to a grid pattern
So imagine an RTS game, with ~150 units all cramped together, just staying chill.
What I would like is to "space them out" so that they d form a grid. This is useful for example when a large ...
2
votes
2answers
74 views
Need help with fixing Optimized Raycasting / Line of Sight algorithm
I'm trying to implement collision detection with raycasting for my 2D javascript game. The game uses equally-sized tiles as its level structure so to optimize collision detecton I'm trying to use a ...
2
votes
0answers
37 views
Finding a path to a circular zone in continuous space [duplicate]
I need to find the shortest path for an agent that wants to use a ranged attack against the specified target. This means that the path's ending point should be inside the range of the attack and have ...
4
votes
2answers
100 views
Can't figure out math for converting negative indices of my voxels and chunks to positives
In my voxel game, I'm trying to spawn chunks in all directions. But since my world starts at 0,0,0, some chunks can spawn at negative positions like ...
0
votes
0answers
55 views
Making a level progression system similar to Bravely Default's
So I am working on an RPG and I want the level up system to be similar to Bravely Default's, which must be similar to how FF classically levels up characters.
What I know about the level up in the ...
1
vote
1answer
34 views
Calculate coordinates of boundaries containing group of objects
I would like to understand how to calculate coordinates of boundaries group of objects as a parallelepiped in 3D game?
Let's say for simplicity we have spheres randomly slowly moving in 3d space some ...
6
votes
1answer
1k views
Efficient algorithm to aggregate a heightmap to a lower resolution
I have a raw 2D height map which consists of cells of the following structure:
...
2
votes
2answers
59 views
what is the fastest way to choose new positions for chunks
I'm having trouble speeding up where I initialise positions for reused / pooled chunks. I found that where I calculate the positions of neighbor chunks, it's even slower than the algorithm I was using,...
4
votes
1answer
84 views
How to maximize enclosed area and minimize perimeter on a grid with obstacles?
Developing an RTS game, I have a tile-based terrain (grid) filled with obstacles. It looks like this (red shapes are obstacles):
Now I need to plan an enclosed area on the terrain with some ...
0
votes
1answer
42 views
Movement within a circle, but the circle bends around obstacles?
I wish I knew a better way to phrase this, but I want to make an object move from point to point inside a circle. But I also want that "circle" to bend around obstacles, so that no matter ...
0
votes
2answers
58 views
Placing a circle as close as possible to a specific coordinate without overlapping another circle
I am working on a 2D game in Java. My goal is to place a ball as close as possible to the center without overlapping the balls that are already there. How can this be done?
2
votes
1answer
129 views
Formula for attack range using hexagons
I need a little help with a formula to calculate the attack range for my turn-based strat game. Since it's a hexagon grid, I'm having trouble coming up with a formula that would pick the character ...
1
vote
1answer
101 views
Getting the point of intersection from this fast ray box intersection algorithm
I have seen lots of such algorithms that return a Boolean value, but I also need to get back the intersection point and ray length.
I am looking into this example, but I'm not sure how I can extract ...
1
vote
1answer
221 views
How does HPA*(Hierarchical Pathfinding A*) really work?
I'm currently researching for a summary paper on the different variants of A* search algorithm and how they are used in games and I stumbled across the name HPA*. I've heard that it's much more faster ...
0
votes
0answers
48 views
Swept AABB vs Line Segment in 2D
I've been trying to get a swept collision detection up and running now for almost a week and I can't for the life of me get it working.
There is a answer on this linked here below:
Swept AABB vs Line ...
4
votes
2answers
261 views
How can I create the arriving/ engaging in combat movement like in StarCraft 2?
I currently have two armies (smaller scale) crashing into each other. They will usually form a line of units fighting. I have no idea how to handle a unit coming from behind the line to properly go ...
0
votes
1answer
42 views
How to properly overflow 2D coordinates on an overflowing/circular map?
I made a simple Snake game designed for trying Snake bots. I thought the base map functions work, but now I found there is an error. What I need is to properly translate any coordinates outside the ...
0
votes
0answers
26 views
How can I detect and hide faces inside an object when combining two or more meshes?
I am trying to make a game where the player can make vehicles out of parts. To apply proper physics to the vehicles, like drag and buoyancy, I would like to get the outer hull of the various parts ...
0
votes
1answer
38 views
Path solving for a game with a similiar pathing mechanic to Anno
I cant quite wrap my head around how to solve pathing in my game. The basic premise is you will place buildings and roads on a 2d field and then you will be able to create routes from one building to ...
0
votes
0answers
26 views
Chess Programming - Principal Variation and Transposition Tables
Right now I am currently trying to implement a principal variation search algorithm for my chess engine (C++) as well as a transposition table. I have looked at various sources online and have become ...
0
votes
2answers
70 views
Tower Defense: Sorting Algorithm with multiple weights (enemy AI)
I'm writing a sorting algorithm for a tower defense mobile game. As a quick synopsis, I have a "tower" that can shoot at incoming threats that are within X distance from the base of the ...
0
votes
0answers
44 views
How to inform pathfinding of solid objects blocking path?
I'm sure this has been asked before, but I couldn't find the thread. Let me know if you can locate the duplicate.
So, I have a my level is an array of tiles, where a tile can either be solid or ...
2
votes
3answers
287 views
Place Buildings to represent village
I try to convert an array of Buildings into a representation of a small village. There are several different buildings in a village, like factories that are located on the outside of the village, ...
0
votes
0answers
34 views
Minimax Algorithm for turn-based game
how should I implement the Minimax Algorithm to a XCOM like turn-based game? I mean I should use score to each action like, move to cover, shoot, fall back etc. Or even is it possible to do that kind ...
0
votes
0answers
10 views
Creating outline from a collection of points following the concavity
I am trying to create an outline from a collection of points. I found this solution for Convex Hull. I specifically picked this implementation: https://en.wikibooks.org/wiki/Algorithm_Implementation/...
0
votes
0answers
60 views
Calculating bounds of a "dirty rectangle"
I'm following noita's GDC (10:30 is where the talk becomes relevant to what I'm doing) to implement various optimization techniques for my falling sand simulation.
The one that's currently blocking me ...
0
votes
1answer
58 views
Parallel transformations tree update
I create my own pet-project graphics engine for the learning and research purposes.
Now I'm trying to create a more efficient scene transformations update technique. My current approach is the linear ...
0
votes
1answer
82 views
Understanding this terrain intersection algorithm
I was looking for a fast way to get a ray intersection point of a terrain defined by a heightmap and I stumbled upon this: https://publications.lib.chalmers.se/records/fulltext/250170/250170.pdf
At ...
1
vote
1answer
40 views
How to get all tiles along a straight vector path?
Let's say I have a 100x100 map of tiles where each tile is 16x16 pixels.
How would I get all tiles along a path? For example, let's say I wanted to get a list of all tiles along the shortest direct ...
1
vote
0answers
57 views
Fast self collision/intersection detection algorithm for tetrahedral meshes
I want to play with deformation of tetrahedral mesh (soft-body simulation) but I need help with self-collision detection stuff.
I found SOFA collision detection but I'm not sure that it fits for self-...
2
votes
1answer
116 views
Determining the price of a trade good depending on supply and demand of a marketplace
I've been meaning to add a market/trading system in my space-themed game where a player can buy from one station and sell it to another for profit, etc. (Examples would be Starsector, Elite: Dangerous,...
0
votes
0answers
20 views
Open world style chunking algorithm help with chunk placement
Hey I have this chunking algorithm I am writing and I cant for the life of me figure out how to place the chunks so they are aligned with each other as if they were in a constant grid. The issue ...
0
votes
1answer
81 views
Isometric tilemap circle around object
I am developing an isometric game like Anno 1602.
I have an isometric tilemap. The default tilesize is 64x31.
My goal is to show the area a building has influence to. For that I want to show a circle ...
0
votes
0answers
37 views
How to fill with empty space with retangles
I have a 'square' class with the representation of its limits from the variables x1, y1 and x2, y1 these variables define points 1 and 3 of the same, in this case the coordinates would be (0,0), (10, -...
0
votes
0answers
97 views
Java Game: Using minimax or similar algorithm for AI battles
Game Info:
Type: grid based ship game; where ships are one-directional (meaning they can only use the allowed moves in the direction it is facing)
Allowed Directions: NORTH,SOUTH,WEST,EAST
Allowed ...
1
vote
1answer
118 views
Determining first voxel ray intersects
I'm trying to implement the Fast Voxel Traversal Algorithm on a uniform grid of axis-aligned rectangles. Having read the paper, I understand how the traversing works, but not the initialization. I've ...
0
votes
0answers
45 views
Seamless tiling?
I'm creating a simple grass/dirt tileset. I'm able to create a seamless tileset by creating 1 unique piece per "direction"... however, this breaks down when trying to create more than one ...
3
votes
3answers
91 views
Calculate min number of moves (no path involved)
I'm looking to implement an algorithm that will calculate the minimum number of moves based on the rules below.
Let's say that we have a grid (NxM), as exampled in the image below.
Each cell will be ...
