Quantcast

Maximum PC

It is currently Fri Dec 19, 2014 12:41 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 33 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Tue Nov 16, 2010 5:11 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dwood15 wrote:
Perl could handle that server idea quite easily, and implement a HiRes timer pretty well.

Personally, I think that tracking the number of client/server queries would be more relevant concerning algorithm performance which is mostly going to tell us who has the best internet connection and/or lives near you.

The other issue with using a network client/server system is that it creates quite a bit of extra work for the client developers (not too mention the server code). How many people here have network programming experience?


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Tue Nov 16, 2010 11:46 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Oh sorry I forgot all the other languages you peeps use can't just place the output in the form of a webpage and send it back a easily as perl can yas? :P


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Nov 17, 2010 5:25 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
I have done a very tiny bit of network stuff... in Java... and most of that was copy and paste to get a stupid app working that was really unrelated to the actual network stuff.

C# handles web just fine Mr Wood! So stuff it. :)


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Nov 17, 2010 10:05 am 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Is that a challenge? :lol:


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Nov 17, 2010 12:14 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Truth be told, I don't have time to... :(

I really need something "fun" to work on.Things have been busy at work and definitely not fun lol.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Nov 17, 2010 3:13 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dwood15 wrote:
Oh sorry I forgot all the other languages you peeps use can't just place the output in the form of a webpage and send it back a easily as perl can yas? :P

Perl can automatically create html output? Interesting...

Perl "just places the output" as an html page? That's pretty cool, but how does it know that I want the output to a matrix placed in a table w/ or w/o borders? That negative values should be colored red? Truth be told, many languages have various degrees of network support built-in... Java, Clojure (by extension... or any language running on the JVM for that matter), C#, Obj-C, Python, Common Lisp and quite a few others to boot. Ansi-C is the only other industry standard language that I can think of offhand where I'm certain there isn't network support built-in (other, less certain, languages would include C++ and Scheme... I'm 50/50 on Smalltalk and Ada).

However, there is another, more important, difference... no other language is nearly as FUGLY as PERL!!! =)


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Nov 17, 2010 3:27 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dwood - If you create the server code, I'll go ahead and write some code to make random mazes of various sizes.*

* Since Perl doesn't seem to have an auto-feature for mazes. ;P


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Nov 17, 2010 4:28 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Gadget wrote:
Dwood15 wrote:
Oh sorry I forgot all the other languages you peeps use can't just place the output in the form of a webpage and send it back a easily as perl can yas? :P

Perl can automatically create html output? Interesting...

Perl "just places the output" as an html page? That's pretty cool, but how does it know that I want the output to a matrix placed in a table w/ or w/o borders? That negative values should be colored red? Truth be told, many languages have various degrees of network support built-in... Java, Clojure (by extension... or any language running on the JVM for that matter), C#, Obj-C, Python, Common Lisp and quite a few others to boot. Ansi-C is the only other industry standard language that I can think of offhand where I'm certain there isn't network support built-in (other, less certain, languages would include C++ and Scheme... I'm 50/50 on Smalltalk and Ada).

However, there is another, more important, difference... no other language is nearly as FUGLY as PERL!!! =)


if ($number < 0) {
print "<b> $number </b>";
}
else { print "$number"; }

I find perl a beautiful language, after having learned the basics but i'm going to need to look up its web items before I jump in to this head first.

As it stands the script would be (imo) incredibly simple. Design the output of the matrices so I know how to work with them, I can design the matrix navigation in less than an hour... I've always been iffy with file input though. ;)

I'll see if I find the time to do it by friday or so.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Tue Nov 23, 2010 10:50 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
I wrote some code that generates mazes in the small to medium size range. In the process, I came up with a different approach for generating large mazes that I may or may not implement depending on how many people get involved with this path-finding project.

I think the symbol encoding that I've used is fairly natural for programming and visual inspection:
S = start location
G = goal location
X = wall location
. = path location

Code:
;;maze1
;;S......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
;;XX.XXX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
;;XX.XXX.XXXXXXXXX.......X........XXXXXXXXXXXXXXXXXXXXXXXXXXXX
;;XX.XXX.XXXXXXXX..X..X....XXXXXX.XXXXXX......XXXXXXXXXXXXXXXX
;;XXXXXX.....XXX..XX.......XXXXXX........XXXX.......XXX......G
;;XXXXXXXXXX..XX.X.X...X..XXXXXXXXXXXXXXXXXXXXXXXXX.....XX....
;;XXXXXXXXXX.XXX.X.XX.......XXXXX...XXXXXXXXXXXXXXXXXXXXXX.XXX
;;XX................X....X.XXXXXX.........XXXXXXXXXXXXXXXX...G
;;XX.XXXX.XXXX...X...X..X..........XXXXXXXXXXXXXXXXXXXXXXXXXXX
;;XX......XXX....X.XX...X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

;;maze3
;;S.XX..X..X......X.........XXXXXXXXXXXXXX.XX.X.X..................X..X.X........G
;;.X.X.....XX...X.X.X..X..X.XXXXXXXXXXXXX...X.X.XX...X.....X.X.....XX...XX........
;;...X.X.X......X.XXXX...X..XXXXXX..XXXXX...X...X..X...X......X......X.....X......
;;....XXX......XX..XX.......XXXXX.X..X.X......X..XX.X....X......X....X...X.X.XX.XG
;;.X..X.........X..X..X...XXXXXX....X..X.....XX........X.....XX..X.X.X............
;;...XX......XX.......X...X.XXX..X......X............X.X.X....XX....X....XXX.XX..G
;;......XX..X...X.X...X......X..XXXXX..X.....X.XX.X.X..X..X...X..X.XXXX..XXX....X.
;;XXXX.....X...X.X..XX.X......X.X........XX..X......X....XXXX.X....X...X.......X..
;;.X.....XX.........XX...XX.XXX.X...XX....XXX..........X..XX....X....X..X....X...G
;;....XXXXX......X.X.....XX...........X...XX....X...X.....XXX....X.X..XX.XX..X...X
;;.XX....X......X.XX.XX.X.....XX......X..XX....XX.X......X.....XXXXXX.....X.......
;;..X.....X..X.....X.XX.X......X...X....X...XX.XX.X...X.XX.XX......X...XX..XX.X..G
;;....X..X.X.X..X..X......X.....X.....XXX......X................XX...X..XX.X..X...
;;XXX..........XXX....X...XX.......X.XXXXXX..X..XX....X..X.XX...XX.X....X..X..X..X
;;XX......X.X.....XX..X..X...X.....X..XXXX...X..X.....X....XXX.X....XXX...X.......
;;.X.X.XXX............XX......X...X.XXXXX.X....X......XXX.X.XXXX....XXXX....X....X
;;.X..X.........X.....X..X...X.XX.X..XXX..X.....X....XXXX.....X.X.X....X......X...
;;.X.X....X..XX..X......X..X.X.X...X...XX..XX....X.XXXXXX.....X....XX.X........XX.
;;...XX..X....X.......X.X..X.X.......XX.X..X........X.XX...X.XXX.X...XX........X..
;;..X....XX..XXX.X...........X....X...X........X.X.........X.....X...XXX......XX..

;;maze4
;;S.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXX.......XXXXXX....XXXX
;;.XXXXXXXXXXXXXXXXXXXXX......XXXXXXXX..........XXXXXXXXXXXX..XXXXX..XXX...X.XXXXX
;;...XXXXXXXXXXXXXXXXXXXX..X........X..XXXXXXXXXXXXXXXXXXXX..XXXXXX.X...XXXX..XXXX
;;XX..XXXXXXXXXXXXXXX......XXXXXXX.....XXXXXXXXXXXXXX...X....XXXXXXXXXXX.XXX..XXXX
;;XX..XXXXXX....XXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXX..XXXXX
;;XX.XXXXXX..XX.......XXXXXXXXXXXXXXXXXXXXXX.........X.XXXXXXXXXXXXXXXXXXXX..X.XXX
;;XX....XX..XXXXXXX...XXXXXXXXXXXXXXXXXX.....XXXXXXXXX.XXXXXXXXXXXXXXXXXXXXX...XXX
;;XXXXX....XXXXXXX..XXXXXXXXXXXXXXXXXXXX.XX..XXXXXXXXX...XXXXXXXXXXXXXXX..XX.....X
;;XXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXX..XXXXXXXXXXX............G
;;XXXXXXXXXXXXX..X.XXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXX
;;XXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXX
;;XXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXX...XXXXXXXXXXXXXXX.XXXXXXX....XXXXXXXXXXXXXXG
;;XXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXX.........XX...XXXXXXXXXXX..
;;XXXXXXXXXXXXXXXX....XXXXXX.......XXXXXXXXXXXXXXXXXXXXXXXXXX...XXXX....XXXXXXXX.X
;;XXXXXXXXXXXXXXXXXXX.XXXXXX.X.....XXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXXXXXX...XXXXXX..
;;XXXXXXXXXXXXXXXXXXX.XXXXXX..X...X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....X....X
;;XXXXXXXXXXXXXXXXXXX.XXXXXX.X.XX.X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX......X...
;;XXXXXXXXXXXXXXXXXXX...XXXX.X.X...X...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........XX.
;;XXXXXXXXXXXXXXXXXXXXX.XXXX.X.......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........X..
;;XXXXXXXXXXXXXXXXXXXXX......X....X...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX......XX..

;;maze5 -- Not generated, just an example of why I think A* is going to have problems w/a maze
;;S............X.XX.XX.X.X.X.X...XXXXXXXXXXXXXXXXXXXXXXXXXXXXG
;;.XXXXXXXXXXX.X.XX.XX.X.X.X.X.X.X...X...X...X...X...XXXXXXXX.
;;.XX..........X.XX.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.....XX.
;;.XX.XXXXXXXXXX.XX.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XXX.XX.
;;.XX............XX.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XXX.XX.
;;.XXXXXXXXXXXXXXXX.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.......XX.
;;.X................XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XXXXX.XX.
;;.X.XXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XXXXX.XX.
;;.X...................X.X.X.X.X.X.X...X...X...X...X.......XX.
;;.XXXXXXXXXXXXXXXXXXXXX.X.X.X.X...XXXXXXXXXXXXXXXXXXXXXXXXXX.
;;.X..................XX.X.X.X.XXXXXX......................XX.
;;.X.X.XXXXXXXXXXXXXX.XX.X.X...XXXXXX.XXXXXXXXXXXXXXXXXXXXXXX.
;;.X.X.X...XXXXXXXXXX.XX.X.XXXXXXXXXX......................XX.
;;.X.X.X.X.X...XXXXXX.XXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXX.
;;.X.X.X.X.X.X.XXXXXX......................................XX.
;;.X.X.X.X.X.X.X...XXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXX.
;;.X.X.X.X.X.X.X.X.X...X...X...X...XX......................XX.
;;.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X..X.XXXXXXXXXXXXXXXXXXXXXXX.
;;.X.X..XX...X...X...X...X...X...XXXX......................XX.
;;.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
;;...X...X.................................................XX.
;;.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XX.
;;.X.X.X.X...........................XXX...................XX.
;;.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXX.
;;.X.X.X.X.........................XXX..X....XX.X.X.X.X.X.XXX.
;;.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXX..X..XX.XX............XX.
;;.X.X.X.X.......................XXX..X..XX..XXXXXXXXXXXXX.XX.
;;.X...X...XXXXXXXXXXXXXXXXXXXXXXXX.....XX.................XX.
;;.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
;;............................................................


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Tue Nov 23, 2010 10:55 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
The forums create a catch-22 with larger mazes. I don't really feel like setting up a gmail account in order to 'share' a few KB of data, but I also don't want to 'break' the pages with larger mazes either. Instead of using the expanded format above, I'll post larger mazes in a run-length encoded (RLE) compressed format. RLE compression should work fairly well for this type of data and is a cinch to code up.

Code:
;;maze 1 example...
(setf m1-enc "1S6.55X1.3X1.55X1.3X1.9X7.1X8.30X1.3X1.8X2.1X2.1X4.6X1.6X6.22X
5.3X2.2X7.6X8.4X7.3X6.1G10X2.2X1.1X1.1X3.1X2.25X5.2X4.10X1.3X1.1X1.2X7.5X3.22
X1.5X16.1X4.1X1.6X9.16X3.1G2X1.4X1.4X3.1X3.1X2.1X10.29X6.3X4.1X1.2X3.1X2.35X")
(setf m1-rows 10)
(setf m1-cols 60)

(defun print-encoded-maze (maze-enc num-rows num-cols)
  "Utility function for printing an RLE maze."
  (let ((maze-dec (rle-dec maze-enc)))
    (loop for i from 1 to num-rows
     for start = 0 then end
     for end = num-cols then (+ end num-cols)
     do (format t "~a~%" (subseq maze-dec start end)))))

(print-encoded-maze m1-enc m1-rows m1-cols)
S......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX.XXX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX.XXX.XXXXXXXXX.......X........XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX.XXX.XXXXXXXX..X..X....XXXXXX.XXXXXX......XXXXXXXXXXXXXXXX
XXXXXX.....XXX..XX.......XXXXXX........XXXX.......XXX......G
XXXXXXXXXX..XX.X.X...X..XXXXXXXXXXXXXXXXXXXXXXXXX.....XX....
XXXXXXXXXX.XXX.X.XX.......XXXXX...XXXXXXXXXXXXXXXXXXXXXX.XXX
XX................X....X.XXXXXX.........XXXXXXXXXXXXXXXX...G
XX.XXXX.XXXX...X...X..X..........XXXXXXXXXXXXXXXXXXXXXXXXXXX
XX......XXX....X.XX...X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Thu Dec 02, 2010 1:41 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Sorry gadget, It's going to take me a little longer to do anything I want to do- my classes just started picking up, entering into crunch time right now so any free time I have I won't want to be on the computer haha, but I'll take a peek at it -eventually- lol.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Tue Dec 14, 2010 6:25 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dwood15 wrote:
Sorry gadget, It's going to take me a little longer to do anything I want to do- my classes just started picking up, entering into crunch time right now so any free time I have I won't want to be on the computer haha, but I'll take a peek at it -eventually- lol.

Huh, what... I thought Perl did all of the work for you?! =)

Good luck on your finals.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Thu Dec 16, 2010 11:57 am 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Gadget wrote:
Dwood15 wrote:
Sorry gadget, It's going to take me a little longer to do anything I want to do- my classes just started picking up, entering into crunch time right now so any free time I have I won't want to be on the computer haha, but I'll take a peek at it -eventually- lol.

Huh, what... I thought Perl did all of the work for you?! =)

Good luck on your finals.


I needed to have system access to do Homework::Study::FinalsForMe;

But the server I'm on which would run it, I don't have access to install the module. (code made for running only in cgi's pffft)


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 33 posts ]  Go to page Previous  1, 2

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group

© 2014 Future US, Inc. All rights reserved.