How does PacMan know where the labyrinth is... or "playing with spatial search"

Started by Yacine, April 11, 2010, 05:53:36 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Should PacMan be realised in Visio?

Yes
10 (100%)
No
0 (0%)
Who cares?
0 (0%)
I would participate
0 (0%)
only over my dead, cold body!
0 (0%)

Total Members Voted: 10

Yacine

Being interested in simulations, I wrote this little shapes pursuing a target. Well, quite boring - the pursuers went straight to the target and you just could move the target around the page to avoid being captured.
Paul posted some while ago a pacman shape.  That was it! Have the shapes travel along a labyrinth, to bring some difficulty in the game.

So far for the idea. Now, how to realise? How will pacman know where the labyrinth paths are? Analyse it's position relatively to a polyline? Too complicated! Set up a labirinth out of single walls and paths? Too much shapes, thus to much work! And pretty unflexible.

The discovery - for me :)! - spatialsearch .  I read some posts from both Junichi and Paul. Waow! So much possibilities. Guys and Girls, you need to explore the world of visio functions outside the shapesheet. Check also spatialneighbors (That's Paul's COLORS ;)) and spatialrelation.

The basic technique being  set, I had to think about how to bind the position of the shapes to the labyrinth paths.  The shape itself was no good for the task. It could only tell me whether it was within the boundaries or not. But, friends - arranged around the main shape - could tell me whether there is a wall on a certain side or not - and still leave the main shape movable. These 4 companions would each call a CALLTHIS macro to ask where they are. The macro, triggered by the FXMOD event, sets a flag in each of the companions: wall/ no wall.

For better flexibility the main shape would tell it's members to which shape (labyrinth) it refers, by a shape data field.

and ... finally, I got lost, writing the actual aim of the game, namely the pursuing formulas. I'd welcome any help from bored visioneers.

Ps: how to use: this PacMan is intended to be moved by the direction keys. You can sheat by dragging it with the mouse, but carfully! As the position is controlled by formulas, it is not obvious bringing it back into the labyrinth, once it is outside.

Pps: Would be fun to finish the project, with "food to eat", lives to lose - once you get captured, and so on... In case of interest, please fill in the poll form.
Yacine

vojo

So why wouldnt you do the following:

- define the center of the paths with lines or line segments
- use the points method to build up arrays of points along the paths
- pacman via CALLTHIS would  test where he is on the points array....
- Check the next point in the array against desired cursor direction
     - if a point there...move to it (update the pointer, move the shape, etc...return)
     - if not....ignore key stroke
- The bad guys could use time approach
     - see the animation code I did about a year ago
     - Here is the tricky part....since the bad guys could on the other side of the sheet....how to pick best path to pacman
         - if you are into masochism....could do a variant of dikstra (sp) to find shortest / cheapest path to pacman....this is not trivial.
     - At any rate...on every tick...recalculate and move to next appropriate point in the array.

Yacine

I just got kissed by the muse again.
If the labyrinth is inverted, ie PacMan is asked to walk outside the path, then connectors could be used to route to the target. The bad guy needs anyhow to know it's target. If we include in it's group a connector (visible first for development, invisible later when playing), we could put it's end point to the pinx and the piny of the target.
One observation I made, is that the connector won't route if the "islands" in the labyrinth are grouped with it. That's an additional case to Junichi's observations regarding spatialsearch. So I had to ungroup the labyrinth.
The enclosed picture and the vsd proof that it works.
To calculate the "bad" path, we would then read out the first rows of the connectors geometry, move there and repeat until we get to the target.

Vojo, thanks for the reply.
I checked your animation post and I can only agree with the other readers - wow.
I loved specially the possibility to "program" the bullseyes. Again VERY nice!
The code however looks as long as "War and Peace", it will take me a while to get behind it.
My animation is not so elaborated: the positions are recalculated by means of a RAND()+... , that gets triggered every time PacMan moves.

In your response you mention the points method. What do you mean by that?
Yacine

vojo

thanks for the kind words.
The key pieces of code I was refering to were
   -the my_timer routine...aka how to make the bad guys move on their own   

most of the rest might be for educational purporses but not sure applicable to this.

There is a function in vba called points.    basically it takes any arbitrary shape and creates a text array of points on long the edges
(you can specify the precision in the case of a curve).   My point is that you could construct such an array from the (hidden) line of the path.   As pacman moves
you can check if the cursor hit is in the points path.  if so, increment the ponter to the next entry in the array....if not do nothing

for example, lest say you have the following line.   
    - start to finish.....[10,10], [10,20], [20,20], [20,30], [30,30]....aka up then to the right then up then to right
    - if pacman at the start...then only up cursior is allowed....up ==> current position ==>[10,10] becomes [10,20]....
      left wont since left is invalid ([10,10] would become [0,10] and that is not in the points array) so current is still [10,10]

the point (no pun intended) is that you could look at this approach vs testing every time all the other shapes in the drawing to see if there is a colision....might be simpler than brute force shape checking
Since its a labyrinth....probably would want an array of points arrays where each points array is a segment.....pacman checks the whole array of arrays incase at an intersection of segments.

Paul Herber

Pacman was a bit after my time, I'm from the XYZZY generation, I'm now lost in a maze of tiny passages, all alike!
Plugh!

Electronic and Electrical engineering, business and software stencils for Visio -

https://www.paulherber.co.uk/