can anybody post me a simple artificial intelligence sample project on path finding.

aditya86b
aditya86b used Ask the Experts™
on
any project with a  basic search algorithm like  minmax, DFS or iterative deepening.
Please post me where can I get a sample papers on A.I topics..

please reply me fast .This is really important .

would be much helpful...

Also check the following threads.I am sorry if I am boring....


http://www.experts-exchange.com/Gamers/Computer_Games/Q_23938747.html

http://www.experts-exchange.com/Programming/Game/AI_Physics/Q_23970008.html
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Commented:
There is some pseudo code in http://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves and
http://en.wikipedia.org/wiki/Alpha-beta_pruning

I haven't heard of DFS.  I only know of minimax, alpha-beta and m & n.  Anyway, what I know is about 30 years old.  Maybe the techniques have been improved since then.


Author

Commented:
DFS means depth  first search.The search algorithm keeps growing till the end of child node
cup

Commented:
Do you mind what language it is in.  I may have some in VBScript/Javascript - basically rewrites of my 1976 Algol 60 coursework.

Author

Commented:
java script or java
cup

Commented:
Sorry, couldn't find the VBScript/Javascript version.  Here is the Fortran77 version.
Header file
! Cannibals and Missionaries
!
! Header file for common blocks
! What we are trying to achieve here is structures.  Unfortunately,
! Fortran77 does not have structures so we just use array indices
! and a two dimensional array as an array of structures.
!**********************************************************************
!     Indices
      integer ixDirn, ixParent, optm, optc
      integer miss, cann, lmiss, lcann, rmiss, rcann
      integer boatLeft, boatRight
      integer ixLo, ixHi, nodemax, opmax
      parameter (
     &    ixLo = -2,
     &    ixHi = 5,
     &    lmiss = -1,
     &    lcann = -2,
     &    ixDirn = 0,       ! direction
     &    rmiss = 1,
     &    rcann = 2,
     &    ixParent = 3,       ! parent index
     &    optm = 4,       ! optimum number of missionaries
     &    optc = 5,       ! optimum number of cannibals
     &    miss = 1,
     &    cann = 2,
     &    boatLeft = -1,   ! boat on left bank
     &    boatRight = 1,   ! boat on right bank
     &    nodemax = 27, opmax = 5)
      common /CnM/
     &     goal,
     &     boat,
     &     node,
     &     path,
     &     unexp
      integer goal(-cann:cann)         ! goal to be achieved
      integer boat(1:opmax, miss:cann) !  legal boat combinations
      integer node(1:nodemax, ixLo:ixHi)! nodes for obtaining soln
      integer path(1:nodemax)          ! the path taken
      integer unexp                    ! index of next unexpanded node
 
Source code
!!*********************************************************************
!! No Copyright - this is Freeware
!!*********************************************************************
!! File:       CnM.f
!! Author:     cup
!!
!! Purpose:
!! Cannibals and missionaries
!!
!! Three missionaries and three cannibals seek to cross a river.  A boat
!! is available which will hold two people and which can be navigated
!! by any combination of missionaries and cannibals involving one or
!! two people.  The cannibals on either bank should not at any time
!! outnumber the missionaries.  The program works out a schedule of
!! crossings that will permit all members of both parties to cross the
!! river safely.
!!
!! This is a Fortran77 conversion of an Algol 60 program I wrote
!! on 15 Dec 1976 as part of the AI module in my Computer Science
!! degree course.  It is an example of how the alpha-beta technique
!! is used.
!!
!!*********************************************************************
      program main
!      include 'CnM.h'
      integer steps
      call Initialize
      call FormPath
      call GetBestPath (steps)
      call PrintPath (steps)
      stop
      end
!**********************************************************************
! Form path.  All the boat combinations are attempted on a node.
! Any legal ones are checked for uniqueness.  If they are unique,
! they will be inserted into the list of nodes.
!**********************************************************************
      subroutine FormPath
      implicit none
!     parameters
!     common
      include 'CnM.h'
!     local
      integer expnd  ! expanded nodes
      logical across ! true when everyone is across
      logical unique ! true if the node is unique
      integer temp(ixLo:ixHi)
      integer op
      integer i
      external GeNz
      logical GeNz
 
      across = .false.
      expnd = 1
      do while (expnd .lt. unexp .and.
     &          unexp .le. nodemax .and.
     &          .not. across)
          temp(ixParent) = expnd
          temp(ixDirn) = -node(expnd,ixDirn)
!         apply the operators held in boat
          op = 1
          do while (op .le. opmax .and. .not. across)
              if (boat(op,miss) .le. node(expnd,-temp(ixDirn)) .and.
     &            boat(op,cann) .le. node(expnd,-2*temp(ixDirn))) then
!                 operator valid for this node
                  temp(optm) = boat(op,miss)
                  temp(optc) = boat(op,cann)
!                 apply the operator and check goal
                  across = goal(ixDirn) .eq. temp(ixDirn)
                  do 30 i = -cann, cann, 1
                      if (i .eq. 0) goto 30
                      temp(i) = node(expnd,i) +
     &                    isign(1, i) * temp(ixDirn)* boat(op,iabs(i))
                      across = across .and. goal(i) .eq. temp(i)
30                continue
                  if (across) then
!                     Everyone across: goal achieved
                      call InsertNode(temp)
                  else if (genz(temp(lmiss), temp(lcann)) .and.
     &                     genz(temp(rmiss), temp(rcann))) then
!                     combination is valid: is it unique?
                      unique = .true.
                      i = unexp - 1
                      do while (i .gt. 0 .and. unique)
!                         no checks are made on columns -1 and -2
!                         since they are dependent on columns 1
!                         and 2
                          unique = temp(rmiss) .ne. node(i,rmiss) .or.
     &                             temp(rcann) .ne. node(i,rcann) .or.
     &                             temp(ixDirn) .ne. node(i,ixDirn)
                          i = i - 1
                      enddo
                      if (unique) call InsertNode(temp)
                  endif
              endif
!             move to next operator
              op = op + 1
          enddo
 
!         move to the next unexpanded item
          expnd = expnd + 1
      enddo
      return
      end
!**********************************************************************
! Check if a path is legal - Greater than or equal to and Non Zero
!**********************************************************************
      logical function GeNz (iMissionary, iCannibal)
      implicit none
!     parameters
      integer iMissionary, iCannibal
 
      GeNz = (iMissionary .eq. 0) .or.
     &       (iMissionary .ge. iCannibal .and. iMissionary .ne. 0)
      return
      end
!**********************************************************************
! Get the path
!**********************************************************************
      subroutine GetBestPath (oSteps)
      implicit none
!     parameters
      integer oSteps
!     common
      include 'CnM.h'
!     local
      integer i
 
!     work backwards to find the parent from the last
!     unexpanded node
      oSteps = 1
      path(oSteps) = unexp - 1
      i = oSteps + 1
      do while (path(oSteps) .ne. 0)
          path(i) = node(path(oSteps),ixParent)
          oSteps = i
          i = i + 1
      enddo
      return
      end
!**********************************************************************
! Initialize the globals
!**********************************************************************
      subroutine Initialize
!     parameters
!     common
      include 'CnM.h'
!     local
      integer temp(ixLo:ixHi)
      
      unexp = 1              ! First unexpanded node
      temp(lmiss) = 3
      temp(lcann) = 3
      temp(rmiss) = 0
      temp(rcann) = 0
      temp(ixDirn) = boatLeft
      temp(ixParent) = 0
      temp(optc) = 0
      temp(optm) = 0
      call InsertNode (temp)
      
!     Valid combinations
      boat(1,miss) = 0
      boat(1,cann) = 2
      
      boat(2,miss) = 0
      boat(2,cann) = 1
      
      boat(3,miss) = 1
      boat(3,cann) = 1
 
      boat(4,miss) = 1
      boat(4,cann) = 0
 
      boat(5,miss) = 2
      boat(5,cann) = 0
 
!     Target to be achieved
      goal(lmiss) = 0
      goal(lcann) = 0
      goal(ixDirn)  = boatRight
      goal(rmiss) = 3
      goal(rcann) = 3
      return
      end
!**********************************************************************
! Insert one array into another
!**********************************************************************
      subroutine InsertNode (iTemp)
      implicit none
!     common
      include 'CnM.h'
!     parameters
      integer iTemp(ixLo:ixHi)
!     local
      integer i
 
      do 10 i = ixLo, ixHi, 1
          node(unexp,i) = iTemp(i)
10    continue
      unexp = unexp + 1
      return
      end
!**********************************************************************
! Print the path
!**********************************************************************
      subroutine PrintPath (iSteps)
      implicit none
!     parameters
      integer iSteps
!     common
      include 'CnM.h'
!     local
      integer i, j
      character*12 direction(boatLeft:boatRight)
      
      direction(boatLeft)  = '   -<<<<<-  '
      direction(boatRight) = '   ->>>>>-  '
      
      print *,'Initially, everyone is on the left bank'
      print *,'Msnry = number of missionaries'
      print *,'Cnnbl = number of cannibals'
      print *
      print *,'  Schedule   Direction       After Crossing'
      print *,'             of Travel   Left Bank  Right Bank'
      print *
      print *,'Msnry Cnnbl             Msnry Cnnbl Msnry Cnnbl'
      do 10 j = iSteps - 1, 1, -1
          i = path(j)
          print '(i4,i6,2x,a12,i4,3i6)',
     &        node(i,optm), node(i,optc),
     &        direction(node(i,ixDirn)),
     &        node(i,lmiss), node(i,lcann),
     &        node(i,rmiss), node(i,rcann)
10    continue
      return
      end

Open in new window

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial