Results 1 to 10 of 15

Thread: SMS Pathfinding code

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1

    SMS Pathfinding code

    I needed a path finding routine for my little Rebelstar game project. I thought I could simply use pathfinding code already written in pascal for the job. This turned out to be more difficult that expected. Hassles with multidimensional dynamic arrays, binary heaps and other oddities that I could easily get working. I finally managed a simple routine working. I don't know who to credit for the original source code as there was no name provided.

    The code is provided as is. I do not think that it is very quick. There is no cost for different terrain or diagonals implemented. However, that should not be too hard to add. Also there is no fancy interface to draw walls etc it is just bare bones.

    http://www.numberworksnwords.com/clo...inding_SMS.zip

    It would be nice to have a better implementation of pathfinding - e..g., a proper Astar with terrain penalties etc
    Last edited by czar; 08-08-2017 at 05:18 AM.
    The views expressed on this programme are bloody good ones. - Fred Dagg

  2. #2
    After throwing a quick look at the provided code it seems this is a "Sample algorithm". This path-finding algorithm is cell based and does not support different terrain weights and rarely even uses different path wight for diagonal paths.
    Extending your algorithm to support diagonal movement won't be so hard as you just need to calculate values for four additional neighboring cells. But if you do plan on having different weight for diagonal movement you will have to change F,G,H to floating point values since cost for diagonal movement would be 1,41.
    And if you want to add different weights based on different terrain you will have to add additional value W to each of your cells. This value stores how difficult is to traverse through certain cell and is usually stored just as multiplier. So you calculate final weight of traveling through that cell by multiplying default wight with this multiplier. So if it is larger than 1 you gain speed boost and if it smaller you are being slowed down.
    Once you add diagonal movement and different cell weights you basically have a cell based A* path-finding algorithm at your hand.
    You can read more about cell based A* path-finding algorithm and how it works here:
    http://www.policyalmanac.org/games/aStarTutorial.htm

    But I would recommend that you rather look for node-based A* path-finding algorithm instead. Why?
    Main advantages of node based path-finding algorithm is that you are no longer limited to the fixed sized grid. You are able to use teleporters for creating shortcuts across your map. And since in node based path-finding each node stores possible paths to other nodes and each of these paths can have its own weight this means that you can have different path weight when going from one A to node B than when going from node B to node A. This is useful for simulating going uphill or downhill.
    Another big advantage of node based path-finding is the ability to implement heuristics path-finding where multiple heuristics levels share same nodes. Somewhere on one of my computers I have nice article about heuristic path-finding but I don't find it right now.
    And another advantage is that it is rather easy to modify the node graph at any time which is very useful when you game have dynamic maps.
    Now the disadvantage of node based path-finding algorithm in comparison to a cell based is that it uses more memory for storing the node-graph. But on today computers I don't think that should pose much problem.

  3. #3
    Thanks Silverwarrior for the pover view and the link. I am aware of the Astar stuff, to be honest I wanted a quick dropping for my little project, and my poor noggin finds pathfinding difficult to work on.

    I did say "no cost for different terrain or diagonals implemented." and that it was a bare bones solution. I have implemented this simple routine for now but I may revisit later if I can solve my other majors challenges. A few other people have responded to me on the SmartMobileStudio forum to highlight two other solutions implemented in SmartMS.
    The views expressed on this programme are bloody good ones. - Fred Dagg

  4. #4
    PGD Staff / News Reporter phibermon's Avatar
    Join Date
    Sep 2009
    Location
    England
    Posts
    524
    There's an interesting addition that's linked to flow fields - when you perform a lot of path finding over an area - you can 'touch' an additional bias variable in each cell and use this additional variable as part of the heuristic calculation at each point. For every cell you look at - minus a small amount from the bias value - then when the final path is found or even better when it's actually walked by an entity - you increase this bias value by twice the amount for every cell that's actually visited.

    This has the effect of increasing the bias for cells that are walked and decreasing it for cells that are rejected.

    Little corners and dead ends end up with very low biases and are rarely checked, because hardly any entities get successful paths through them and thus don't bias them. A corridor connecting two parts of a base would have big bias value etc.

    So ultimately you get a kind of 'heat map' of the most regularly traversed cells and the heuristic bias means that these cells are considered first when path finding - greatly reducing the number of cells that are actually checked for all but the most uncommon of paths.

    To make it a true flow field - instead of storing this bias heuristic as a single number - store it as a vector and add the direction the path takes over that cell as a bias vector - so you get further reductions in places where just a distance heuristic alone wouldn't favour one or the other direction.

    I hope that makes sense - the idea is to check as few cells as possible.

    --

    Another useful technique is to store previous paths, each path themselves having a bias. Then when you path from one point to another - before walking the cells, you run through the start/end points of stored paths - from the most strongly biased paths to the least biased paths - and you see if your destination and your starting point are close to the start and end of any existing path.

    If it is? then just work out the path to get to and from either end of that existing path - then you've just turned a big expensive path calculation into two small ones and a couple of linked list insertions.

    It can get complicated with path merging - minimising how often it happens for different biases etc - but it's interesting
    When the moon hits your eye like a big pizza pie - that's an extinction level impact event.

  5. #5
    Quote Originally Posted by phibermon View Post
    I hope that makes sense - the idea is to check as few cells as possible.
    I believe this approach is being used in game Prison Architect and until now I haven't really understood how it works. But thanks to your description I do now.

  6. #6
    Game specific optimization but interesting nerveless

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Comodo SSL