Point-Click-Move

After a few beers last night and mucking about with models I remembered that someone asked about clicking on a grid or map and having an object walk to that point. So here is some code I knocked out. Be warned its very rough and has a rotation bug (:oops:) which I am sure is easy to fix but its only an example. I was deeply under the affluence of incahol at the time :smiley:

Obviously if your dealing with objects on a grid, then you would need some path finding like A*. Check out gamedev for a nice tut on this.

The board.py is taken from the chess tutorial and needs the square.egg file in your models directory to work.

Have fun!

boardWalker.py

from math import sqrt
from direct.interval.IntervalGlobal import *
from direct.actor import Actor

class BoardWalker(DirectObject):

  def __init__(self, modelPath, walkingModelPath, pos, hpr, scale,
               rotationOffset = 0, movementSpeed = 0.5):
    self.actor = Actor.Actor(modelPath, {'walk':walkingModelPath})
    self.actor.setScale(scale, scale, scale)
    self.actor.reparentTo(render)
    self.actor.setPos(pos)
    self.actor.setHpr(hpr[0], hpr[1], hpr[2])
    self.rotationOffset = rotationOffset
    self.accept('actor-stopped', self.__stopWalkAnim)
    self.actorMovement = None
    self.movementSpeed = movementSpeed
    
  def moveTo(self, position):
    if self.actorMovement != None:
        self.actorMovement.pause()
        self.__stopWalkAnim()
        
    # This is the "start" position
    sPos = self.actor.getPos()

    # Calculate the new hpr
    # Create a tmp NodePath and set it to the start position
    # Then make it "lookAt" the position we want to be at.
    # It will then create the hpr that we can turn to.
    a = NodePath('tmp')
    a.setPos(sPos)
    a.lookAt(position)
    newHpr = a.getHpr()

    # Create a turn animation from current hpr to the calculated new hpr.
    actorTurn = self.actor.hprInterval(1,
                                       Point3(newHpr[0] + self.rotationOffset,
                                              newHpr[1],
                                              newHpr[2]),
                                       startHpr = self.actor.getHpr())

    # Calculate the distance between the start and finish positions.
    # This is then used to calculate the duration it should take to
    # travel to the new coordinate base on self.movementSpeed
    if sPos[0] > position[0]:
      distanceX = sPos[0] - position[0]
    else:
      distanceX = position[0] - sPos[0]
    
    if sPos[1] > position[1]:
      distanceY = sPos[1] - position[1]
    else:
      distanceY = position[1] - sPos[1]

    distance = sqrt((distanceX * distanceX) + (distanceY * distanceY))
    
    # Create a movement animation using the 2 positions
    actorMove = self.actor.posInterval( (distance / self.movementSpeed), position, startPos = sPos)

    # But the animations into a sequnce and create an event that will be
    # called when its finished.
    self.actorMovement = Sequence(actorTurn, actorMove, name = 'actorMove')
    self.actorMovement.setDoneEvent('actor-stopped')

    # startFrame, stopFrame, playRate, loop
    #self.actorMovement.setupPlay(-1, -1, 5, 0)

    # Start the walking animation, then start the turn+move anims
    self.actor.loop('walk')
    self.actorMovement.start()

  def __stopWalkAnim(self):
    # This is called when the turn+move anim has finished.
    # We can then stop the walk anim.
    self.actor.stop('walk')
    self.actorMovement = None

board.py

import direct.directbase.DirectStart
from pandac.PandaModules import *
from direct.interval.IntervalGlobal import *
from direct.gui.DirectGui import *
from direct.actor import Actor

from boardWalker import *

#First we define some contants for the colors
BLACK = Vec4(0,0,0,1)
WHITE = Vec4(1,1,1,1)
HIGHLIGHT = Vec4(0,1,1,1)
PIECEBLACK = Vec4(.15, .15, .15, 1)

#This is derived from the mathmatical of a plane, solved for a given point
def PointAtZ(z, point, vec):
  return point + vec * ((z-point.getZ()) / vec.getZ())

#A handy little function for getting the proper position for a given square
def SquarePos(i):
  return Point3((i%8) - 3.5, int(i/8) - 3.5, 0)

#Helper function for determining wheter a square should be white or black
#The modulo operations (%) generate the every-other pattern of a chess-board
def SquareColor(i):
  if (i + ((i/8)%2))%2: return BLACK
  else: return WHITE

class Board(DirectObject):

  def __init__(self):
    self.accept('escape', sys.exit)              #Escape quits
    base.disableMouse()                          #Disble mouse camera control
    camera.setPosHpr(0, -13.75, 6, 0, -25, 0)    #Set the camera
    self.setupLights()                           #Setup default lighting

    #Since we are using collision detection to do picking, we set it up like
    #any other collision detection system with a traverser and a handler
    self.picker = CollisionTraverser()            #Make a traverser
    self.pq     = CollisionHandlerQueue()         #Make a handler
    #Make a collision node for our picker ray
    self.pickerNode = CollisionNode('mouseRay')
    #Attach that node to the camera since the ray will need to be positioned
    #relative to it
    self.pickerNP = camera.attachNewNode(self.pickerNode)
    #Everything to be picked will use bit 1. This way if we were doing other
    #collision we could seperate it
    self.pickerNode.setFromCollideMask(BitMask32.bit(1))
    self.pickerRay = CollisionRay()               #Make our ray
    self.pickerNode.addSolid(self.pickerRay)      #Add it to the collision node
    #Register the ray as something that can cause collisions
    self.picker.addCollider(self.pickerNode, self.pq)
    #self.picker.showCollisions(render)

    #Now we create the chess board and its pieces

    #We will attach all of the squares to their own root. This way we can do the
    #collision pass just on the sqaures and save the time of checking the rest
    #of the scene
    self.squareRoot = render.attachNewNode("squareRoot")
    
    #For each square
    self.squares = [None for i in range(64)]
    for i in range(64):
      #Load, parent, color, and position the model (a single square polygon)
      self.squares[i] = loader.loadModelCopy("models/square")
      self.squares[i].reparentTo(self.squareRoot)
      self.squares[i].setPos(SquarePos(i))
      self.squares[i].setColor(SquareColor(i))
      #Set the model itself to be collideable with the ray. If this model was
      #any more complex than a single polygon, you should set up a collision
      #sphere around it instead. But for single polygons this works fine.
      self.squares[i].find("**/polygon").node().setIntoCollideMask(
        BitMask32.bit(1))
      #Set a tag on the square's node so we can look up what square this is
      #later during the collision pass
      self.squares[i].find("**/polygon").node().setTag('square', str(i))

      #We will use this variable as a pointer to whatever piece is currently
      #in this square
      self.squares[i].piece = None

    # Load in the actor
    self.boardWalker = BoardWalker('models/panda-model',
                                   'models/panda-walk4',
                                   SquarePos(1),
                                   [0, 0, 0],
                                   0.001,
                                   180)

    #This will represent the index of the currently highlited square
    self.hiSq = False
    #This wil represent the index of the square where currently dragged piece
    #was grabbed from
    self.dragging = False

    #Start the task that handles the picking
    self.mouseTask = taskMgr.add(self.mouseTask, 'mouseTask')
    self.accept('mouse1', self.selectSquare)       #left-click grabs a piece

  def mouseTask(self, task):
    #This task deals with the highlighting and dragging based on the mouse
    
    #First, clear the current highlight
    if self.hiSq is not False:
      self.squares[self.hiSq].setColor(SquareColor(self.hiSq))
      self.hiSq = False
      
    #Check to see if we can access the mouse. We need it to do anything else
    if base.mouseWatcherNode.hasMouse():
      #get the mouse position
      mpos = base.mouseWatcherNode.getMouse()
      
      #Set the position of the ray based on the mouse position
      self.pickerRay.setFromLens(base.camNode, mpos.getX(), mpos.getY())
      
      #Do the actual collision pass (Do it only on the squares for
      #efficiency purposes)
      self.picker.traverse(self.squareRoot)
      if self.pq.getNumEntries() > 0:
        #if we have hit something, sort the hits so that the closest
        #is first, and highlight that node
        self.pq.sortEntries()
        i = int(self.pq.getEntry(0).getIntoNode().getTag('square'))
        #Set the highlight on the picked square
        self.squares[i].setColor(HIGHLIGHT)
        self.hiSq = i
          
    return Task.cont

  def selectSquare(self):
    if self.hiSq != None:
      self.boardWalker.moveTo(SquarePos(self.hiSq))
    
  def setupLights(self):    #This function sets up some default lighting
    lAttrib = LightAttrib.makeAllOff()
    ambientLight = AmbientLight( "ambientLight" )
    ambientLight.setColor( Vec4(.8, .8, .8, 1) )
    lAttrib = lAttrib.addLight( ambientLight )
    directionalLight = DirectionalLight( "directionalLight" )
    directionalLight.setDirection( Vec3( 0, 45, -45 ) )
    directionalLight.setColor( Vec4( 0.2, 0.2, 0.2, 1 ) )
    lAttrib = lAttrib.addLight( directionalLight )
    render.attachNewNode( directionalLight.upcastToPandaNode() ) 
    render.attachNewNode( ambientLight.upcastToPandaNode() ) 
    render.node().setAttrib( lAttrib )


#Do the main initialization and start 3D rendering
w = Board()
run()

A million billion thanks and blessings Sandman worship worship!

It was me who asked about mouse point & click controls. I did try to figure it out by myself, but it was simply beyond my poor noob abilities.

Thankyou, thankyou, thankyou for this :smiley:.

Glad you found that helpful Pesky.

Last night I hit the beer again and produced the following example in python for A* path finding. You might find this helpful aswell. Its not linked to panda3d and will need changing to suit your needs. But Im sure it will guide you in the right direction, if not already be 90% there.

It sacrifices memory for speed but I really think something like this should be done in c/c++ and not in python. But I guess it depends on what your after.

Also note that the grid(map) is 1 dimensional. People often think of a map in 2 dimensions but thats actually slow for computers as they like a long list of numbers :wink:

I have tried to unroll and combine some of the checks done to help speed it up a little ( Im sure someone better in python than me will show me an even faster way to speed things up :slight_smile: ) and that part is a little unreadable, but I did try to comment some of the parts to explain whats going on.

A couple more things,
The grid starts at a coord of 0, 0. I.e. the first cell is located at 0, 0.
If the X size of a grid is 10, then thats 0 to 9.
To convert a 2d coord to a grid coord then, posX + ( posY * gridSizeX )

Hope you find it useful,

Take care

# **********************************
# * Programmed by : The_Sandman    *
# * Class Name    : PathFinder     *
# * Revision      : 0.10           *
# * UK Date       : 08/09/2005     *
# * Thanks To     : Gamedev        *
# * License       : As You See Fit *
# **********************************

# -- Basic A* algorithm description --
# G = weight of the square ( 10 for parrallel, 14 for diagonal )
# H = Manhatten distance to target (10 for each unit)
# F = G + H

# The squares are layedout like this for explanation
# 1 2 3
# 4 0 5
# 6 7 8
#
# 0 will always be parent (current square being processed)

# parent = startPos
# Do
#   put parent on closed list
#   For n = 1 to 8 (adjacent squares to parent)
#    If square(n) is NOT on closed list (We have already been down that route)
#      If square(n) is on open list,  (Its already been calculated)
#        *Could the current parent be a better parent?*
#        newG = weight + parent.G
#        If newG < square(n).G then,
#          square(n).G = newG
#          square(n).parent = parent
#          square(n).F = square(n).H + square(n).G
#      Else
#        square(n).Parent = parent
#        square(n).H = (Manhatten Distance to goal) * 10
#        square(n).G = (14 for diagonal else 10) + parent.G
#        square(n).F = square(n).H + square(n).G
#        put square(n) on open list
#   parent = The square with the lowest F on open list
#   If parent = target
#     Route found.
#   If openList contains no squares (nodes)
#     No route found
# Loop
# parent will be the end of the path.
# go through each node parent to give the full path in reverse order.


class PathNode:
  def __init__(self):
    self.parent = 0
    self.x = 0
    self.y = 0
    self.h = 0
    self.g = 0
    self.f = 0

class PathFinder:
  def __init__(self, sizeX = 0, sizeY = 0):

    # These are node states, should really be constants
    self.__NODE_NOT_DEFINED = 0
    self.__NODE_OPEN        = 1
    self.__NODE_CLOSED      = 2


    # The sizes of the grid
    self.__sizeX = sizeX
    self.__sizeY = sizeY
    size = sizeX * sizeY

    # The grid is a 1 dimensional list and not 2 dimensional
    # It stores movement values. 0 is a walkable square,
    # 8 is non-walkable.  It is possible to use 1-7 for "friction".
    # Say, walking on a road has a weight of 1 but grass has a weight of 3
    # Therefore the pathfinder will try to use paths involving roads unless
    # it goes too far out the way. - See calcNode for a little more info.
    self.__grid      = [0 for i in range(size)]
    self.__openList  = [0 for i in range(size)]
    self.__nodeID    = [0 for i in range(size)]
    self.__nodeList  = [PathNode() for i in range(size)]
    self.__nodeState = [self.__NODE_NOT_DEFINED for i in range(size)]

    # Default values.  Although the relevent ones are reset when
    # findPath() is called.
    self.__nodeListSize = 0
    self.__openListSize = 0
    self.__closedListSize = 0

    self.__targetX = 0
    self.__targetY = 0
    self.__temp = 0
    self.__tempNode = None
    self.__nodeNumber = 0
    self.__parentNumber = 0

    # For testing Ive put the map into this routine.
    self.__grid[ 4 + ( 3 * sizeX ) ] = 8
    self.__grid[ 4 + ( 4 * sizeX ) ] = 8
    self.__grid[ 4 + ( 5 * sizeX ) ] = 8

  def findPath(self, startX = 0, startY = 0, targetX = 0, targetY = 0):

    # Reset the node states each time we look for a path
    self.__nodeState = [self.__NODE_NOT_DEFINED for i in range(self.__sizeX * self.__sizeY)]

    # Setup default values
    self.__nodeListSize = 1   # This is 1 because we fill in the startpos
    self.__openListSize = 0
    self.__closedListSize = 0

    # Save the target as calcNode() will use it aswell
    self.__targetX = targetX
    self.__targetY = targetY
    
    # Build the start Node
    self.__tempNode = self.__nodeList[0]
    self.__tempNode.x = startX
    self.__tempNode.y = startY
    self.__tempNode.g = 0
    self.__tempNode.parent = -1
    
    # Set the starting parent, which is the start coord
    self.__parentNumber = 0
    
    # These are explained below
    gridNumberM = 0
    gridNumberL = 0
    gridNumberR = 0

    # For testing I used an abort incase of infinate loop.
    # It should be safe(ish) to remove this now
    abort = 0

    # Here we start the process off.
    # Loop until we have no more paths to check
    while self.__parentNumber != -1:

      # For testing I set this to 150 (a 10x10 map should loop max 100 times)
      abort += 1
      if abort == 150:
        print 'PathFinder: Possible Infinate Loop : Aborting'
        return

      # startX and startY are really the current X and Y locations.
      startX = self.__nodeList[self.__parentNumber].x
      startY = self.__nodeList[self.__parentNumber].y

      # If we have now hit the target, we can break the loop
      if startX == targetX and startY == targetY:
        break

      # These gridNumbers refer to the Middle(0)/Bottom(2)/Top(7) squares
      # in the grid.  Should help save a few calcs.
      gridNumberM = startX + ( startY * self.__sizeX )
      gridNumberB = gridNumberM - self.__sizeX
      gridNumberT = gridNumberM + self.__sizeX

      # Mark the parent as being closed
      self.__nodeState[gridNumberM] = self.__NODE_CLOSED
       
      # Calc all adjacent squares
      # Square numbers mentioned in text below are..
      #   1 2 3
      #   4 0 5   0 == Parent (this square)
      #   6 7 8

      # The below might seem long-winded but in reality its just
      # unrolled loops and checks.
      # Check squares 1-8 so they are in the grid range sizeX, sizeY
      # Check squares 1, 3, 6 and 8 to see if they can be "walked" to.
      #  I.e. Dont cut through part of a wall
      # Call the calcNode function for the square


      # First check bottom(2) and top(7) squares.

      # Range check to test below square 0
      if startY > 0:

        # Is square 2 walkable?
        if self.__grid[gridNumberB] != 8:

          # Calc square 2
          self.__calcNode(gridNumberB, startX, startY - 1, 10)

      # Range check to test above square 0
      if startY < self.__sizeY:

        # Is square 7 walkable?
        if self.__grid[gridNumberT] != 8:
          # Calc square 7
          self.__calcNode(gridNumberT, startX, startY + 1, 10)

      # This section checks the left of 0 and then the diagonals
      # on that side ( 1 and 6 )

      # Range check to make sure we can test left of square 0
      if startX > 0:

        # If sqaure 4 is unwalkable then we cant
        # get to squares 1 and 6 aswell.
        if self.__grid[gridNumberM - 1] != 8:

          # Calc square 4
          self.__calcNode(gridNumberM - 1, startX - 1, startY, 10)

          # Range check to make sure we can test below square 0
          if startY > 0:

            # If square 2 is unwalkable then we cant get to square 1
            if self.__grid[gridNumberB] != 8:

              # Is square 1 walkable?
              if self.__grid[gridNumberB - 1] != 8:

                # Calc square 1
                self.__calcNode(gridNumberB - 1, startX - 1, startY - 1, 14)

          # Range check to make sure we can check above square 0
          if startY < self.__sizeY:

            # If square 7 is unwalkable then we cant get to square 6
            if self.__grid[gridNumberT] != 8:

              # Is square 1 walkable?
              if self.__grid[gridNumberT - 1] != 8:

                # Calc square 6
                self.__calcNode(gridNumberT - 1, startX - 1, startY + 1, 14)


      # This section checks the right of 0 and then the diagonals
      # on that side ( 3 and 8 )

      # Range check to make sure we can test right of square 0
      if startX < self.__sizeX:

        # If square 5 is unwalkable then we cant
        # get to squares 3 and 8 aswell.
        if self.__grid[gridNumberM + 1] != 8:

          # Calc square 5
          self.__calcNode(gridNumberM + 1, startX + 1, startY, 10)

          # Range check to make sure we can test below square 0
          if startY > 0:

            # If square 2 is unwalkable then we cant get to square 3 
            if self.__grid[gridNumberB] != 8:

              # Is square 3 walkable?
              if self.__grid[gridNumberB + 1] != 8:

                # Calc square 3
                self.__calcNode(gridNumberB + 1, startX + 1, startY - 1, 14)

          # Range check to make sure we can test above square 0
          if startY < self.__sizeY:

            # If square 7 is unwalkable then we cant get to square 8
            if self.__grid[gridNumberT] != 8:

              # Is square 8 walkable?
              if self.__grid[gridNumberT + 1] != 8:

                # Calc square 8
                self.__calcNode(gridNumberT + 1, startX + 1, startY + 1, 14)
    
      # If the open list contains no more nodes,
      # then we have checked every possible path
      # and there is no route.
      if self.__openListSize == 0:
        self.__parentNumber = -1
      else:
        # The new parent will be at the top of the open list
        # as that will contain the lowest F score.
        self.__openListSize -= 1
        self.__parentNumber = self.__openList[self.__openListSize]

    # End of While
        
    if self.__parentNumber == -1:
      # No route!
      print 'No route found'
    else:
      print '--REVERSE PATH DUMP--'
      while self.__parentNumber > -1:
        print '%i, %i' % (self.__nodeList[self.__parentNumber].x,
                          self.__nodeList[self.__parentNumber].y)
        self.__parentNumber = self.__nodeList[self.__parentNumber].parent

  def __calcNode(self, gridPos, x, y, weight):

    #Check the node state to see if it has been defined
    if self.__nodeState[gridPos] == self.__NODE_NOT_DEFINED:

      # Create the new node details
      self.__tempNode = self.__nodeList[self.__nodeListSize]
      self.__tempNode.parent = self.__parentNumber
      self.__tempNode.x = x
      self.__tempNode.y = y

      # If you wanted to add weights for road, grass, etc then
      # you will need to add self.__grid[gridPos] to the g values
      # of the node.  Note: That needs to be done here and for
      # when the node is updated in the NODE_OPEN part below.
      self.__tempNode.g = weight + self.__nodeList[self.__parentNumber].g
      self.__tempNode.h = (10 * (abs(self.__targetX - x) + abs(self.__targetY - y)))
      self.__tempNode.f = self.__tempNode.g + self.__tempNode.h

      # Each node thats added to the list is given an ID for its gridPosition.
      # This is stored in nodeID.  This can then be used to find a node
      # based on its gridPos.  Thinking about it, its only relevant if we
      # are resizing memory.  This could be removed and all nodes are generated
      # at their gridPos since the lists are sized to the max anyway!
      # But it means that we need to clean out that memory next time findPath
      # is run - That may be too intensive.
      self.__nodeID[gridPos] = self.__nodeListSize

      # The node location is added to the open list.
      self.__openList[self.__openListSize] = self.__nodeListSize

      # The node list size has changed.
      self.__nodeListSize += 1

      # nodeNumber is used as a temp.
      self.__nodeNumber = self.__openListSize

      # The open list size has changed.
      self.__openListSize += 1

      # Move the node down the open list based on its F score.
      # This will keep the lowest F score at the top (end) of the list
      while self.__nodeNumber > 0:
        if (self.__nodeList[self.__openList[self.__nodeNumber]].f >
            self.__nodeList[self.__openList[self.__nodeNumber - 1]].f):
          self.__temp = self.__openList[self.__nodeNumber]
          self.__openList[self.__nodeNumber] = self.__openList[self.__nodeNumber - 1]
          self.__openList[self.__nodeNumber - 1] = self.__temp
        else:
          break
        self.__nodeNumber -= 1

      # End of while
        
      # Mark this node as now being open
      self.__nodeState[gridPos] = self.__NODE_OPEN

    elif self.__nodeState[gridPos] == self.__NODE_OPEN:
      # If its already been opened, then we need to see if this parent
      # is a better parent than the origional one.
      self.__nodeNumber = self.__nodeID[gridPos]

      # If you wanted to add weights for road, grass, etc then
      # you will need to add self.__grid[gridPos] to the g values
      # of the node.  Note: That needs to be done here and for
      # when the node is created in the NODE_NOT_DEFINED part above.
      self.__temp = weight + self.__nodeList[self.__parentNumber].g

      # Is this a better parent for the open node?
      if self.__temp < self.__nodeList[self.__nodeNumber].g:

        # If so, then update this nodes details to the new parent
        self.__tempNode        = self.__nodeList[self.__nodeNumber]
        self.__tempNode.g      = self.__temp
        self.__tempNode.parent = self.__parentNumber
        self.__tempNode.f      = self.__temp + self.__tempNode.h
            
        # Move the node down the open list based on its F score.
        # This will keep the lowest F score at the top (end) of the list

        while self.__nodeNumber > 0:
          if (self.__nodeList[self.__openList[self.__nodeNumber]].f >
              self.__nodeList[self.__openList[self.__nodeNumber - 1]].f):
            self.__temp = self.__openList[self.__nodeNumber]
            self.__openList[self.__nodeNumber] = self.__openList[self.__nodeNumber - 1]
            self.__openList[self.__nodeNumber - 1] = self.__temp
          else:
            return
            
          self.__nodeNumber -= 1

        #end while


# Tell the path finder we will use a 10x10 grid
# At the moment, this is pretty pointless as I am generating
# a blank grid with a wall on it in the PathFinder init
aStar = PathFinder(10, 10)

# Find me a path from 2,3 to 8,3
aStar.findPath( 2, 3, 8, 3)

This is brilliant stuff Sandman, thankyou very, very much.

If this is the kind of thing you do when youโ€™re drunk, then I hope you get enebriated more often, :wink:.

Thanks again.