Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

5
votes
1answer
2k views

What makes a path finding heuristic Monotonic vs. Non-monotonic?

I am currently working on an algorithm that solves a path through the maze. So far I have implemented a Manhattan and Pythagorean Heuristic. I was wondering what makes a heuristic monotonic and how ...
0
votes
1answer
27 views

Generate a HexMap where each tile has a different tile on each edge

I’m trying to generate a 7*13 hexmap, with 9 different types of tiles, numbered 0 through 8. I need the map to be randomly generated on each run and it has to be so that each tile has a different ...
1
vote
2answers
399 views

How to allow character to keep moving after it hits a wall

I am developing an iPhone game. There is a fountain that the user should not be able to walk through. Now, this question is about checking circle-point collision or anything like that. I am checking ...
2
votes
2answers
67 views

Pathfinding with non-deterministic transitions between nodes

Consider a map not unlike a board game, where some of the moves are made non-deterministic. For example, moving onto certain cells will require you to roll a dice to determine where you should move ...
4
votes
2answers
254 views

How to implement n-body in an Entity Component System

Recently I've been throwing problems at Entity Component Systems to see how far I can push the paradigm. One problem in particular I struggle with, which is writing an elegant implementation of the n-...
2
votes
2answers
62 views

2D walled map generation

I want to make a 2D walled map. the walls must be L,T,+,-,| shaped. (made from vertical and horizontal lines) There must not be a complete closed block (i.e. all parts of the map must be connected). ...
0
votes
1answer
78 views

Acceleration in Unity

I am trying to emulate acceleration and deceleration in Unity. I have written to code to generate a track in Unity and place an object at a specific location on the track based on time. The result ...
15
votes
3answers
25k views

Sorting array of points in clockwise order

Is there such an algorithm to sort an array of 2D points in clockwise order? I'm specifically dealing with right triangle in my case so only 3 points. However I'm interested in knowing if such an ...
0
votes
2answers
44 views

Weighted random events with conditions

I'm building a system for distributing ingame events for a strategy game. The game is heavily driven by the events and each country/player should receive one or more per time unit. The algorithm is ...
4
votes
3answers
240 views

Image-Space coherence of the z-buffer algorithm

I'm reading Hierarchical z-Buffer Visibility by Ned Greene et al. and they state that traditional Z buffering makes reasonably good use of image-space coherence in the course of scan conversion. I ...
0
votes
1answer
20 views

Score multiplier based on lowest time

I'm making a score system that will be based on several factors, how many collectibles you have obtained, how few hits you have taken, etc. I want to add in a multiplier based on how quickly the ...
0
votes
1answer
69 views

How to use grammars for procedural generation?

I am working on a system to procedural generate a house using this article. I am trying to understand how grammars work and are made I have found very little information on the topic online. From my ...
2
votes
1answer
794 views

merging box colliders for optimizing

Look at the picture. The figure on the left shows the individual box collders in green. The yellow boxes on the right are the results of the optimization of the original box colliders. What is the ...
2
votes
1answer
535 views

What's the best way to deal with platformer tile collisions?

I am starting with game development and creating a basic platformer game. I already have searched a lot and found some ways to implement the platformer aspect to the game, like apply a gravity, ...
0
votes
1answer
54 views

Unity3D: activeSelf issues

I've been trying to script some basic AI for a Unity Roll-A-Ball game, which involves two balls collecting cubes for points (one controlled by the player and the other controlled by AI. Everything ...
16
votes
6answers
7k views

What's the best way of transforming a 2D vector into the closest 8-way compass direction?

If you have a 2D vector expressed as x and y, what's a good way of transforming that into the closest compass direction? e.g. ...
4
votes
3answers
580 views

Space nebula cloud generation?

I found a cool kickstarter project called "Skywanders". It's an minecraft like space game with a lego like building system and pretty cool graphics. One thing I noticed are the "nebula clouds". They ...
8
votes
2answers
1k views

How to create a map from graph

I want to draw a 2d polygon map based on data provided by another source to ease analysing actions on the map. The data has the following format: ...
1
vote
1answer
95 views

Looking for a square-to-hex pixel coords algorithm

So as the headline suggests, I am looking for an algorithm/algorithms used for square-to-hex and hex-to-square pixel coordinates convertion. I have an image which looks kinda "interpolated", meaning ...
1
vote
2answers
197 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 ...
1
vote
0answers
25 views

Team matchmaking based on ELO score

I'm looking for a very simple way to put up 2 teams out of unspecified amount of players. So its not actually a standard matchmaking since it only creates one match out of the whole pool of queued ...
0
votes
1answer
350 views

A* algorithm works silly with heap

I'm trying to use A* and visualised it, but when i add a heap optimization it start looking in incredeble ways sometimes normal(better then next to be sure), somtimes he looks on few columns. Normal ...
14
votes
2answers
2k views

How to gain accurate results with Painter's algorithm?

A while ago I asked how to determine when a face is overlapping another. The advice was to use a Z-buffer. However, I cannot use a Z-buffer in my current project and hence I would like to use the ...
1
vote
1answer
212 views

How simulate a random distribution?

I'm working on a battle algorithm for a text-based game and I stumble when it comes to randomly distributing attacks on a set of units. E.G, 100 archers shoot 100 targets at the same time. I thought ...
6
votes
2answers
695 views

How to choose inputs to an artifial neural network?

I have to implement, as part of an assignment, a learning method that enables minesweepers to avoid colliding with mines. I have been given the choice to choose between a supervised/unsupervised/...
5
votes
2answers
3k views

Catmull Rom Spline - Constant Speed

Given the equations found in the answer here: Determine arc-length of a Catmull-Rom spline to move at a constant speed How would one A) Apply this to a 3D Catmull-Rom Spline, and B) write A out ...
1
vote
1answer
221 views

Tic Tac Toe Victory State Detection [closed]

Below is the code I'm using to check if the board state has a tic tac toe style victory state. The board is always square and is made of an array of objects that keep track of their own completion ...
5
votes
1answer
182 views

How to randomly create a fair maze for a multiplayer game?

I am creating a 2d multiplayer RTS game which happens inside a maze. I have used Growing Tree algorithm to randomly generate the maze. I thought that the maze would be fair for each team as long as ...
3
votes
2answers
2k views

How does transvoxel algorithm work and how can I implement It?

After wasting over three days of researching on DuckDuckGo/Google, trying to understand transvoxel paper and existing implementation, I come here to clarify the subject for me and made it easier for ...
1
vote
1answer
93 views

Dynamic Tilemap size changer

I have started coding this project using the library SFML a few months ago. I have implemented a random map generation everytime I load the game thanks to Biome and the Perlin noise Algorithm. I ...
0
votes
1answer
122 views

Can you use A* to make a unit move nonspecifically?

A* is typically used to calculate the best way to move towards something, and it's quite flexible when it comes to threats, extra movement costs, and 'refuelling' on the way to something. However, if ...
0
votes
0answers
21 views

Duplicate packets and termination of packets in multiplayer game

I'm making a multiplayer game (lazertag) with real hardware. After hours of research, I'm choosing the UDP instead of the TCP protocol to exchange data. Because of how unreliable UDP is and because ...
1
vote
0answers
17 views

Handling game message packet loss at low speed and at a microcontroller level

I read this: How do I handle packet loss in a client-server network model? ...But I'm looking for more advice. Currently I'm implementing my own lazertag vests. I'm programming hardware (8051 ...
0
votes
1answer
26 views

Getting an object to move in another objects direction

I have a player and an enemy, both have x and y values, and I want to move the enemy to the player and have them 'touch' over time in a speed that I can determine, I tried calculating the angle ...
-1
votes
1answer
56 views

Java 2d array to generate grid - java.lang.ArrayIndexOutOfBoundsException: length=4; index=-1

I am creating a Hashi Puzzle game (Islands and Bridges) I am generating a 2d grid with Islands that can be connected using bridges, I am also running a DFS algorithm to check if the map is solvable I ...
1
vote
5answers
232 views

How can I select an enemy to act next, biased toward smaller enemies?

Suppose there are X number of enemies in the game. They all have to attack one by one. Each enemy is picked randomly, and can be of Y size. How can we attain biased randomness in such a way that ...
1
vote
1answer
71 views

How to find sequences of consecutive cards of the same suit in a hand, including wild cards? (Indian Rummy)

I have a hand of 13 cards (chosen from 2 standard decks of 52 cards + 4 jokers, so it's possible for the same card to appear multiple times). I want to search this deck to find sequences according to ...
3
votes
1answer
181 views

Creating random path in grid

I need to find a path with required length in the NxN matrix without loops and deadlocks. For example: We Have a grid 7x7 (49 blocks in total) with START (orange) point. We need to build random ...
10
votes
2answers
9k views

How to calculate delta time with SDL?

I have heard that you can calculate delta time with two functions called SDL_GetPerformanceCounter and SDL_GetPerformanceFrequency. I'm not sure how they work completely, but I heard it is a bit ...
0
votes
2answers
166 views

Quick algorithm to identify undrawn rectangles inside a map

I already have a working algorithm for this but it's home-made and there is some redundancy in the things it checks, so I'm looking for a fast algorithm (or the name of it) that would detect undrawn ...
0
votes
0answers
31 views

Instancing Meshes With Overdraw Algorith

I am working on a Game Engine(DX11) and we are at a point where we are starting to cull, and order our objects in the scene for rendering order. However, since we want to instance the same mesh, ...
7
votes
3answers
2k views

Evolutionary Procedural Generation [closed]

Are there any examples of companies or papers using evolutionary algorithms (EA) or genetic programming (GP) in procedural generation of content for games? Does this exist in the industry? This is ...
3
votes
3answers
415 views

Divide rectangular image into fixed number of random sized rectangles + 1 fixed size rectangle

I'm trying to divide a rectangular image into a fixed number of smaller rectangular image parts (of random but bounded width / height), with the exception of 1 rectangle which is predefined in ...
1
vote
1answer
307 views

Welzl Algorithm to find the Smallest Bounding Sphere

I'm implementing Welzl's Algorithm to find the Smallest Bounding Sphere. In brief, the algorithm works by maintaining: a set of points to contain in the sphere (inside its interior, or on its ...
7
votes
2answers
803 views

Algorithm to reduce a bitmap mask to a list of rectangles?

Before I go spend an afternoon writing this myself, I thought I'd ask if there was an implementation already available --even just as a reference. The first image is an example of a bitmap mask that I ...
1
vote
1answer
277 views

How to combine dynamic asset reload and texture atlases? (rectangle packing with removal)

Usually texture atlases are built either: as a seperate content pre-processing step or once when the game starts What I want to do is create and update atlases on the fly when: A new texture file ...
11
votes
1answer
2k views

Triangulation A* (TA*) pathfinding algorithm

I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81. He describes how to adapt the regular A* ...
2
votes
1answer
386 views

Dynamically creating astar node map by triangular polygonal map

My game's map format uses a bunch of triangles to make up the platforms and terrain in 2d. Right now I can set up a 2d array of nodes for the A* (A star) algorithm that basically is a bunch of ...
4
votes
1answer
310 views

Create shape from points / lines in editor and mathematically calculate nearest points within shape

If I want an editor that accepts "points" of a minimum of three (a triangle) and I just add some points first, like this: how can I mathematically connect these corners (points) into an object of ...
0
votes
1answer
134 views

Removing duplicate vertices on a mesh

I have a set of vertices and another set of indices. Sometimes I find that I have duplicate vertices in my mesh. I tried at first to check if two identical vertices were in the array of vertices but ...