(v01 08-12-22)

mystar

Cart File | Forum Post |

	More cartridges by dw817

More Cartridges [View All]

 

mystar

by dw817

Cart #mystar-2 | 2022-08-12 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

6

VVhat's New ?

(08-12-22)

• Gave each room a name based upon its shape and design.
• Increased from 11 to 16 sample rooms to explore and find exits to.
• Improved search routine, is faster and more efficient.

Once the program is loaded, press a key to continue.
then use LEFT ⬅️ and RIGHT ➡️ arrow keys to select a default wall and 🅐 and 🅑 arrangement. Or if you don't want one, just choose the first one seen here, "The Void" (#1) and press 🅾️ to continue.

Now you can use the arrow keys to navigate. Move the cursor on top of the 🅐 or 🅑 block and press 🅾️ to lift it up. Then press 🅾️ to place it in the new location. You can only drop 🅐 or 🅑 on a blank tile, not a wall. To cancel the move and return the 🄰 or 🄱 block back to its original position, press ❎.

Press 🅾️ on a block or empty square to add or remove a block there.

When you are all set, press ❎ to initiate search for from 🅐 to 🅑. Hold down the 🅾️ key to run it faster. When complete you will return back to the map editor.

There is a common method for finding the shortest path of point A to B called A*Star. It is fairly complex as you can see:

https://en.wikipedia.org/wiki/A*_search_algorithm

Having examined this and watched many Youtube videos later on the subject, I just thought to myself, there has to be an easier way to do this. There must be !

Now what classic A*Star does is determine the distance between two points A and B, it also determines the distance for going in a possible direction to seek out B, using square root and exponents, and if it runs into a dead-end, it must backtrack, lock off that direction, follow its new thread of commands, and try a different path.

No easy feat to code.

So I puzzled and puzzled till my puzzler was sore. And then thought surely it must have something to do with PAINT. I mean I wrote a paint routine years ago in Pico-8 and it touches all points except those that are blocked off.

So - I realized right then I COULD write a program that determines if its even possible to reach destination B from A - to ensure that it wasn't blocked off by a wall or other obstacle.

So I wrote that, and it worked. But then I thought, how can I make a path from A to B not really worrying about the distance for the moment ?

Well according to the original A*Star they check distances between points. So let me create a large 8x8 field for the screen and plot 2-digit numbers on the distance from there to the target, and - maybe follow the distances by going up by one each time.

While that worked pretty neat with no walls, once you added walls it quickly got stuck, and I was not sure of how to get around these.

So I gave it more thought. What if - what if I were to say point A is 1 and draw 2 around it and 3 around that, etc. Sort of like a multi-colored fill routine, giving a nice outline around the whole thing till it was done. In doing this I am not tracking the distance but where the seeker is at the moment of its iteration.

Well that certainly created an interesting display. Maybe then just follow the numbers from 1 to its end A to B ?

Yes, that works, but not all the time. If there was more than one path to reach point B my program would not guarantee to pick the shortest path each time, and it could also get stuck in a dead end. But I was getting closer to what I wanted.

So I thought again - how do I solve mazes ? Well, I CHEAT. :) That is if I really get stuck then instead I start from the END and work my way to the beginning.

So I reversed points, so the 1 started at point B and then I sent out my "paint" routine till it hit point "A" as there was no point in continuing to fill the screen once "A" was found.

And that looked better. The numbers were there. I didn't want to count backwards though so I added in the code to reverse the numbers recorded once target A was reached. So instead of from nn to 1 it was 1 to nn.

Then I took my finger and traced. I was closer but the tracking of the number was unpredictable when I did a diagonal movement.

And it's not like I ever wanted any diagonal movement in the grid-games I write anyways. So I changed my paint to not paint 8-tiles outward, but 4, the same as a player could move.

Well that worked and it certainly found the path but it took a terrible way to do it. Trailing all the way across horizontally in a straight-line and finally down.

Now while this was the same length as trailing manually with my finger, it didn't look right.

So I thought about it again. Why not do this ? Seek L R U D for if (x+y) mod 2 = 0 and U D L R if not.

The reason for the (x+y) means that it would automatically swap back and forth for every horizontal or vertical movement but not for diagonal, giving diagonal movement using only U D L R movements.

And that got it !

My*Star would now track in a neat diagonal line flipping from horizontal to vertical if the target was more easily reached that way.

And it worked. I could make 2 or more paths and because of the way my paint added numbers to the screen, it guaranteed the shortest path every time !

So after about a week of fighting this, I present to you my own offering for pathfinding, not AStar but MyStar, using my own method of pathfinding.

It may not be faster than A*Star but at least for me (and likely you) what I wrote is a lot easier to understand and follow.

And there it is ! Try it out for yourself to see if you can get it not to find the shortest path.

Also if you have any questions or comments, please let me know in the field below.

This was a very interesting read!

Hi @profpatonildo:

Thank you for your interest !

And while I don't think I'm going to win any mathematical medals (except gold stars are welcome :) ) for what I developed here, it does show that some complex things such as algorithms can be improved upon if examined closely.

I actually developed something like this for a simple board-game years ago, taking advantage of a table of numbers that solved the problem of where to move before you needed to ask the computer - it only needed to rely on the table of fixed numbers based upon where the player moved last.

If I can find the time I'll try to release it for Pico-8.

A good friend of mine told me that if you want to get something done quickly and efficiently, find a lazy person to do it. For they will have the best and easiest way to accomplish that task - far better than conventional means.

I have always been a bit lazy in that respect. :)

Please do release that as well! These sorts of technical carts are very informative and helpful!

I don't mean to diminish your work, but this looks like a Dijkstra map.

I recently implemented it in a roguelike I'm working on because it's a perfect use case. All of the enemies are seeking the player, so running it once per turn solves pathfinding to the player for all enemies.

I did it a bit differently, though, following the approach outlined here:
https://www.redblobgames.com/pathfinding/tower-defense/

Also, it's worth noting that it's not always required to find the full path to the target, depending on the logic used by enemies, etc. Once the distances for each tile have been determined, they can be saved as a property of that tile. Then, when the enemy is looking to move toward the target, they simply choose the neighboring tile with the lowest distance property (or in the case of your example, since you're reversing the order, the highest).

A Dijkstra map. Let me see ...

OMy it does look like it, @binaryeye. Here I'm thinking I'm all original cause I avoided the cursed A*Star and there is something like this that exists.

Well my Dad did tell me that great minds run in the same channel. :)

I remember when I was 7-years old I thought I discovered binary by drawing 3-circles on paper and telling Dad I could count from nothing to 7 with them by putting pennies in each or not at all.

Despite the fact it exists it is not going to take the wind out of my sails. I still discovered it on my own even if it existed previously. I certainly didn't see a mention of it as I was reading A*Star.+

And there are still a few things I can do in coding I see nowhere else.

What you mentioned is interesting. I'll read up on "Dijkstra" now that I know the name of it.

Also can you please post an example of code using this, "property of tile" method ?

. . .

I have looked up, "Dijkstra" in Wikipedia. Interesting stuff.

I am not convinced they are doing what I am. Mine is quite a bit simpler than this:

Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

For instance, I am not calculating any distance at all any time during its run. I am making a "pearl" is the best way to describe it. That is, I start with 1 which is a grain of sand and then smooth it over with 2, that 2 with 3, that 3 with 4, etc. and only stop once it touches its target.

So ... it may be similar but it is not Dijkstra in that at no time am I ever examining the distance between the two points. So I'm still feeling pretty proud of myself for developing a path finding algorithm that is so easy to understand and follow.

Not now but later I have an update to the My*Star program. It runs faster, more efficiently, and is more intelligent now. I will post that after I get back from writing a book chapter, different subject matter.

By "property", I just mean values stored in a table. I don't know that I can post any relevant code.

I store a map of the level as a 2D array of "tiles", with each entry a table of various bits of info about that tile. Tile type, whether the tile is occupied, whether the tile is visible by the player, etc. One of these bits of info is the distance of that tile to the player, using the Dijkstra method. Each turn, the Dijkstra method updates the distance to the player for each tile. Referencing the properties looks like this: map[x][y].distance, map[x][y].occupied, etc.

"Dijkstra map" is a term used in roguelike development to describe a process that uses the concept of Dijkstra's algorithm and applies it to a 2D grid of uniform distance. Since the distance between adjacent, connected points is the same, there's no need to measure distance; it's done indirectly by incrementing by 1 each step farther from the target.

The article I linked earlier has good information for implementation, but this article is probably a more obvious visualization:
http://www.roguebasin.com/index.php/Dijkstra_Maps_Visualized

Below is a basic version of what I'm using in my project.

function dmap(target_x, target_y)

  -- create a 2D table to hold distances for each tile on the map
  -- give each tile an arbitrarily high distance
  local distance = {}
  for ix = 0, 30 do
    distance[ix] = {}
    for iy = 0, 26 do
      distance[ix][iy] = 9999
    end
  end

  -- create a table to hold tiles at the frontier (edge of outward expansion)
  local frontier = {}

  -- add the target tile to the frontier
  local tile = {
    x = target_x,
    y = target_y
  }
  add(frontier, tile)

  -- set the distance of the target tile to zero
  distance[tile.x][tile.y] = 0

  while #frontier > 0 do
    -- iterate through all tiles in the frontier
    for t in all(frontier) do
      -- note the distance of the current tile
      local current_tile_distance = distance[t.x][t.y]
      for i = 0, 3 do
        -- check adjacent tiles in the cardinal directions
        local d = key_direction[i]
        local ax = t.x + d.x
        local ay = t.y + d.y
        -- if the adjacent tile is passable and hasn't yet been traversed (i.e. distance is 9999)
        if map[ax][ay].passable and distance[ax][ay] == 9999 then
          -- set the distance of the adjacent tile to the current tile's distance + 1
          distance[ax][ay] = current_tile_distance + 1
          -- and add the adjacent tile to the frontier
          local tile = {
            x = ax,
            y = ay
          }
          add(frontier, tile)
        end
      end
      -- after all adjacent tiles have been checked, remove the tile from the frontier
      del(frontier, t)
    end
  end

end

The 2D table "map" is a global defined elsewhere, and only referenced here to check if a tile is passable (e.g. floor not wall). "key_direction" is a simple global helper:

key_direction = {
  [0] = {x = -1, y = 0},
  [1] = {x = 1, y = 0},
  [2] = {x = 0, y = -1},
  [3] = {x = 0, y = 1}
}

Hi @binaryeye. As for key directions, I am already doing this, well, sort of. Mine varies according to (X+Y)%2.

As for the distance, I state once again I am not using distance calculations in my code.

And now that I'm back I'll make that simple game I had in mind.