0

Assume that we have have this grid with coordinates. enter image description here

We start at 0.0 (it's actully 0,0 but my Libre Office cannot handle 0,0 due to my settings) and we want to go to -3.10

Is there any search algorithm for this type of problem? Start position and stop position can change too.

This is a math question and I'm pretty sure that this is well used in game development, but I have not found any algorithm that can handle these kind of problems.

euraad
  • 2,934
  • Adjacency of cells in your pictorial representation might correspond to the existence of an edge between two vertices in a network (or 'graph'). Then I guess you are looking for the shortest path between two vertices? – Ali Feb 10 '20 at 17:12
  • @Ali yes. Shortest path is from start to stop is what I'm looking for. – euraad Feb 10 '20 at 17:13
  • Have you looked through https://en.wikipedia.org/wiki/Shortest_path_problem? – Ali Feb 10 '20 at 17:16
  • @Ali Thanks! But what is most used? There is lot's of algorithm out there. Most of them works only in theory. – euraad Feb 10 '20 at 17:17
  • @Ali Can I use Simplex method for this? – euraad Feb 10 '20 at 17:28
  • I don’t know your simplex method but a cheap to implement algorithm is the $A^{}$-algorithm, which is commonly used in games (indie games at least). You may also look up Dijkstra‘s algorithm. – Jonas Linssen Feb 10 '20 at 18:05
  • @PrudiiArca Thanks! What do you prefer? A* or Dijkstra? – euraad Feb 10 '20 at 18:08
  • @PrudiiArca Found C code for Dijkstra https://www.codewithc.com/dijkstras-algorithm-in-c/ – euraad Feb 10 '20 at 18:08
  • 1
    I have learnt about Dijkstra about five years ago, so I don’t know about its performance. Since A-star is commonly tought in game programming tutorials I guess it is faster or easier to implement (or both) – Jonas Linssen Feb 10 '20 at 18:11
  • @PrudiiArca Ok! I will take A* then. Thanks for the information. – euraad Feb 10 '20 at 18:14

0 Answers0