Stack Exchange Network

Stack Exchange network consists of 175 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.

0
votes
0answers
21 views

Seamless UV painting in 3d

I have a 3d model with UV and texture. User sets 2 points on the screen, then I calculating UV's of theese 2 points using Möller–Trumbore intersection algorithm, bake a few times using interpolation ...
1
vote
2answers
66 views

Binary space partitioning with floor as an object

I have a conceptual problem. The problems comes with the floor I'm rendering and the count of objects. The idea was to reduce rendering with BSP implementation, but the problem that I hit was that the ...
0
votes
0answers
26 views

Chess AI Finding Checkmate Using MinMax

I have implemented a chess AI using a Mini-Max(With a partially working AB pruning) implementation. At the moment, it can search a depth of 5 and it is capable of playing a good middle-game. It pretty ...
1
vote
1answer
80 views

A* heuristic for use with Goal Oriented Action Planner

Many of the high-level descriptions I've found for GOAP and similar planners suggest using A* for their path-finding, but I'm struggling to implement it for my own planner. Specifically, I'm ...
1
vote
2answers
55 views

Timed Line Drawing

I'm trying to program a remake of the classic Missile Command Atari game from scratch, but I've run into a problem. So I have a function that can draw a line from one point to another. I figured I ...
0
votes
1answer
42 views

Instantiate prefabs at particular vectors using text file (Unity3D game)

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 Unity3D game (c# script). The locations are ...
3
votes
1answer
1k views

How can I tell if an object in a tile grid is surrounded?

I'm making a game which uses a 10x20 matrix to store the position of the objects. I have a castle object, represented by a number in a matrix. It is randomly deployed in some cell of the matrix. I ...
0
votes
1answer
67 views

A* Quad/Oc Tree path-finding vs Navigation Mesh path-finding

Main What are the differences between those path-finding algorithms. Is Navigation Mesh faster in finding the path? Is it more correct than Quad/Oc Tree? Does Navigation Mesh use Quad/Oc tree under ...
0
votes
1answer
68 views

Get a Jump normal gravity based on Attractor Points, lines or Quad placed in the Level Design (in a Mario galaxy like gravity)

I have an algorithme to find. I have a player in a 3D space on a random planet. My goal is to have an oriented gravity toward my planet. And when I jump: Find the right normal direction. BUT I can't ...
24
votes
11answers
3k views

What are your favourite game-specific coding gems? [closed]

I'll start off with John Carmack's the Fast Inverse Square Root in Quake III: ...
1
vote
1answer
116 views

Diamond Square Algorithm - How to fix horrible diamond shaped artefacts and spikes?

I was attempting to follow this article explaining the implementation of a wrapping version of the diamond square algorithm. I tried running it with dimensions of 128x128 and a "feature size" of 16, ...
1
vote
1answer
56 views

Composing Game Metrics

So I'm running into a bit of a roadblock with the way I'm currently keeping track of game metrics. By "metrics", I mean little bits of information that I can compose together to get useful information ...
0
votes
0answers
28 views

Detect how many blocks can be moved given a grid of blocks

Let G be a grid of booleans where true means a block is there and false means there isn't a block there. Let P be the player, ...
67
votes
7answers
14k views

How does A* pathfinding work?

I would like to understand on a fundamental level the way in which A* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.
0
votes
0answers
23 views

Unity — Proper algorithm for a Character Controller that automatically fits mesh?

I'm trying to make an algorithm that will automatically generate a CharacterController component (on a parent-GameObject) which should automatically resize to whatever the current mesh size is. To ...
4
votes
2answers
2k views

What algorithm to use to fill a KenKen square board with cages?

I am working on recreating KenKen, a popular math puzzle involving a blank grid that is divided into "cages". Each cage is just a collection of adjacent squares and has a clue which is generally a ...
20
votes
4answers
19k views

Calculating minimum velocity of the projectile needed to hit target in parabolic arc

If I have a point which I want to hit at the end or during a parabolic arc, how would I calculate the needed x and y velocity?
0
votes
1answer
41 views

Steering constantly turning in circles

I've been working on a fish system in a compute shader but bugs have been drowning me. The latest bug had me strip almost all the functionality to track down: Fish keep turning in circles. It starts ...
3
votes
2answers
1k views

understanding spatial hash function behaviour and Knuth for int64

I implemented open-indexing sparse 2D spatial HashMap, and I'm quite satisified with performance ( ~30-70 CPU cycles to get object at particular location for size ~16 Milion objects ). However, I ...
17
votes
7answers
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. ...
22
votes
3answers
38k views

How can I create a random “world” in a tile engine?

I am designing a game that is working on a classic tile engine, but whose world is generated randomly. Are there existing games or algorithms that do this? The procedural generation algorithms I have ...
7
votes
2answers
449 views

100 points between 0-1000 on an increasing scale

Basically, it's for roleplay, I need to generate 100 points along a scale. Level 1 is the starting amount, and is at point 0 on the scale. Level 100 is the highest amount planned at this point, and it ...
3
votes
2answers
107 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
0answers
45 views

Slot Probability Function

Please can someone point me in the right direction. I'm working on a slot game. that I'm having trouble figuring how to implement the probability function for. The game has a set of symbols that bets ...
0
votes
2answers
223 views

Algorithm to detect impossible scenarios

I'm making a simple game where a surface is split up into 4 parts, rows, obstacles spawn in them, and a player tries to dodge them. Up to 3 obstacles are generated in each row, and this can lead to ...
5
votes
1answer
3k 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
48 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
403 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 ...
4
votes
2answers
332 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
72 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
88 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
64 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
246 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
106 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
893 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
544 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
83 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 ...
4
votes
3answers
675 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
98 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
219 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
39 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
376 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
215 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
716 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
273 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 ...