Messages

Here's another static screen with the interface removed. 



Another hint:

Spoiler

the surrounding interface was all text... including the description of this scene.

[close]

Do you mean a game with "pieces" that could be mixed and matched by the player to create new rooms and puzzles in real time?

No.  This is a static screen...

Hint:  It's an old adventure game.  It was available on a many platforms.

Here it is... Interface removed.

[Digger]

Digger   (to be fair:  my wife walked by and said, "That's the game I used to play on the Atari 800!"  So... she got it.)

Amazing look!  I'm going to have to go kosher! 

Anything new, Khris?  Was that demo in the engine, script, or other?  I was not able to download the link.

I was thinking... if you did code that in AGS, a module might be able to provide improve path-finding (although, not elegantly).  Anyway, just some random thoughts to bump this thread.  I hope to be able to get enough "hobby time" to get into some coding again soon. 

At the worst:  We now have AGS path-finding documented, and by using the grid above as a check, no one should ever have a broken or ridiculously inefficient walkable area again.

I thought I'd throw one together while winding down this evening... 

Looking into the Petri dish I say, "Finally! [burp]  My cloning technique is perfected!  Now, all I need is a body, and I can resurrect the late Maestro and his orchestral genius."

Nice progress! I have not gone back to this since last week.  Looks like a good start...

Gribbler grot it!

Here's a little history of this classic game.

Next hint:  The computer it ran on was made by Radio Shack.

A hint:  It's 80's.  ...  early 80's.

Okay... if you insist. 

I think Captain D gets the win.  "Fedora Spade"

But, then, this looks amazing...

Polygon Example Video.

Is this guy on the forums?   

It looks like some good ideas are brewing! 

I put an implementation of A* in the engine last night.  It works.  It's not that much more efficient than the Dijkstra search (Search A), but I have not spent any time on optimizations.  It does visit fewer nodes... as it should... fwiw.   

I'm thinking of improving it by spacing the nodes like this:



Starting from the orange location and using the Euclidean distance from each center point as the heuristic, it would follow this this path to get to the yellow destination.   When the path is found, the character would follow the line from the parent's center to the location.  This allows pixel-perfect paths, created in the same raster-painting tool used for the backgrounds, but with fewer nodes to search.



But even as I write this, I'm thinking:  Wouldn't it be sufficient to just use waypoints?  I kind of like having pixel-perfect walkable masks, and the moment is not slow in general -- it's the path-finding.  We only really need to find a path through areas that cannot be traversed directly, and this is what the engine currently does.  We only go to path-finding when the destination is not within sight.    So, if we added waypoints with a line-of-sight check at each point, wouldn't this solve the problems?  I might be missing something here...



It would be so so easy to implement a proof of concept that the next time I'm in the engine's code I'll throw one together. 

(Although, I should have put that left vertex a little bit closer to the bend to keep the player for making strange turns or backtracking, but that's an adjustment left to the person dropping the vertices)

It may be related to the bug with straight line movements. By the way, have you look at it? I'm curious to understand what is wrong with the "old pathfinder".

While I cannot give you an answer (yet) for the odd movement in the opposite direction (!), I can tell you a few things about this bug.

First, you are correct in assuming that the "old" path finding system is at fault (Search B in this thread).  It is broken.  As you observed in the source code, when you are moving along a straight line, AGS forces this search.  The comment says that it's for key presses (I have not investigated anything related to keyboard movement).  In the case that you set up, it returned a very unusual path.  The path finding system does not use any trigonometry.  The path following system does.  I did not look into any trigonometric issues, because the old method was moving so slowly on this large map that I stopped looking into the problem.  I think any solution to these bugs will involve a rewrite of the system, discarding Search B.

Abandoning Search B, I forced the engine to use Search A, and the expected behavior took place.   The player moved to the lower right hand corner of the screen.



In this partial screenshot, you can see Search A finding the proper path.  Now, I'm not sure if this is part of your bug, but just FYI, the "proper" path will be the lower left hand corner of the screen.  This might be counter-intuitive, but I think AGSers have been used to this behavior.   When you click outside of a walkable area, AGS looks for the closest walkable area to your chosen location by doing a distance calculation from every other pixel (3 pix granularity) in a 100x100 square around your chosen location.  If this fails, AGS searches the entire screen at a 5 pixel granularity, doing distance calculations.  These attempts are represented in the screen above as blue circles.  The large blue circle is the "found" location.  This is where AGS assumes you want to go, even though you have chosen a point much further away in a non-walkable area. 

Again FYI, the first movement in your test works correctly because the path finding system is not involved at all.  When you move around in a large area without any obstacles, AGS simply moves the character along a straight line. 

[EDIT:  Answer below]

Okay... the bug with Search B was "bugging" me, so I took one more look.   Here's the issue.  The problem is with your walkable area.  The bug in Search B causes it to "double back" when it hits a boundary.  In your case, it hit a "snag" (a pixel) and doubled back to the location on the right.  Then your original (AGS chosen blue circle) was within the line of sight, so the engine went there, back to the left.  If you smooth out this corner, the bug that you've reported goes away.  It's still there, but your new walkable area avoids it.  It's not intrinsic to straight lines movements.  It's just another side effect of the older, broken path finding code.

...at least this is my theory based on observation, not tracing the code.

You (all) are too kind.  I really haven't done anything yet... Let's wait and see if I can make an actual contribution (like the programmers that have been around here for a long time), and see if I can make this a little better!  This is just one little piece of a project that has generated amazing games for over a decade, and I am enjoying sinking my teeth into it.  After a hiatus of just about as much time, getting back into game development is helping me keep my head clear! 

At the very least, path finding is a little more "documented" now. 

I would really like to play around with optimizing this code when I have a chance!

Interesting read. When drawing the three pixel grid, does it have to be perfectly aligned with the room edges?

To answer your question, I will post a few screens. 

First: A tool for everyone.  The following screen is the "grid."   You can use it to look at your backgrounds, play with pathfinding, etc. 



Second: Below is a test room with a 1 pixel path connecting two areas. 



Although I did not back out all of my changes to the iteration limits on Search B in order to confirm my theory, I believe that the engine, as is, will also navigate a similar 1-pixel path using AGS's original pathfinding algorithm.  It's just that you can make a map where Search B will always fail, because it's broken.  Plus, you really don't want to perform two searches every time the player moves in your game.  Search B is slower.

You can see the good ol' Captain walking right on the grid below (this is a later screen shot from when I starting testing the player's starting position).



Now, here's the caveat:  While testing this, there was one time when the grid did not match up.    I was surprised, but I almost starting writing a post saying that the search will start from the player's position, even though I could never get a different grid to draw, and even though I was 99% positive that I wasn't missing some variable, some constant, some anything anywhere, in the code.   However, I went back in and set the player's starting position as (0,0) then (1,0), (2,0), (3,0), (1,1), (1,2), and a few more, and the player followed the grid every time.  What did I see?   I have no idea.  I could not get it to happen twice.  Of course, I was not running it in C++ debugger at the time, so I could not break and watch the variables.    So...   "buyer beware"?    "Your mileage may vary."    I wish I could say something concrete...

Anyway, I'd do some more investigation, but I'm out of time for today.  It's off to "real (non-programmer) life."