Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Pathifinding
Index -> Programming, Turing -> Turing Submissions
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Raknarg




PostPosted: Wed Jun 13, 2012 10:02 pm   Post subject: Pathifinding

I've been working on this for my class, and I decided to show it. Maybe someone can find this useful.

All it basically does is find the shortest path from point a to b, and retraces its shortest steps from b to a. Also, if it finds b at one point, it never takes more than as many steps required for that path. It can shorten the processing times in some situations. It's just brute forcing mostly, so it's nothing special. I just like looking at it XD



Pathfinding.t
 Description:

Download
 Filename:  Pathfinding.t
 Filesize:  3.4 KB
 Downloaded:  310 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
Beastinonyou




PostPosted: Mon Jun 18, 2012 11:42 am   Post subject: Re: Pathifinding

Interesting =P. I myself am looking into A* and how to apply it. If I can get A* working, I'd like to then try using Binary Heaps in it. It's all very intriguing;

Good Tutorial: A* : http://www.policyalmanac.org/games/aStarTutorial.htm
Even Better: Binary Heaps in A*: http://www.policyalmanac.org/games/binaryHeaps.htm

A Path finding Module would be quite handy if it can be adapted well, and I'd assume would be a well sought-after module.


My 2 cents =P
Raknarg




PostPosted: Mon Jun 18, 2012 12:50 pm   Post subject: RE:Pathifinding

Interesting. Might be a fun summer project.
evildaddy911




PostPosted: Thu Jun 28, 2012 10:38 am   Post subject: RE:Pathifinding

ive been trying to get one working using A*, but i ran into a syntax problem: it wont let me use flexible arrays as a parameter:

Turing:
type xy:
record
     x,y:int
end record
procedure AStar (... var path: flexible array 1..* of xy)
*
*
*
end AStar
gives me a syntax error
any ideas on how to get around that?
mirhagk




PostPosted: Thu Jun 28, 2012 10:55 am   Post subject: RE:Pathifinding

You can pass arrays without knowing the upper bound in turing, it won't be flexible in the procedure though.
evildaddy911




PostPosted: Thu Jun 28, 2012 12:04 pm   Post subject: RE:Pathifinding

well the point of the flexible part was so i can resize it to the length of the path... i guess the only real way to do it is to make use a regular array, make it a function that returns the length of the path?
mirhagk




PostPosted: Thu Jun 28, 2012 1:24 pm   Post subject: RE:Pathifinding

Well you might be able to implement your own flexible array, having it return a pointer, but yeah it's probably best to just use a regular array and return the length.
Raknarg




PostPosted: Thu Jun 28, 2012 9:20 pm   Post subject: RE:Pathifinding

Actually, I would work with a linked list on this problem instead. That way you can keep track of all the branches. It's like a flexible web array, much better to work with seeing as it's not linear.

Ever heard of those, evildaddy?
Sponsor
Sponsor
Sponsor
sponsor
mirhagk




PostPosted: Fri Jun 29, 2012 7:25 am   Post subject: RE:Pathifinding

I'd be scared to see how a linked list works in Turing lol.
evildaddy911




PostPosted: Sat Jun 30, 2012 9:12 am   Post subject: Re: Pathifinding

ive heard of linked lists, but i have no idea how to use them... i did the static array/return size, works pretty well, heres the result:
the file also contains a randomize_map procedure, parameters are the map array, the width of the map, the height, the percent chance that a square will be open and an array of squares that need to be open and have an available path to all of them.



AStar proc.t
 Description:

Download
 Filename:  AStar proc.t
 Filesize:  6.05 KB
 Downloaded:  172 Time(s)

Raknarg




PostPosted: Sat Jun 30, 2012 5:43 pm   Post subject: Re: Pathifinding

Actually, mirhagk, they are awesome as far as I can tell. I made a neat program with it, a self building 20 questions type game. Just make a text file to go with it calle 20Qs.txt like this:

name of an animal
nil
nil

It reads and writes the file.



Linked Lists - 20 Questions.t
 Description:

Download
 Filename:  Linked Lists - 20 Questions.t
 Filesize:  2.76 KB
 Downloaded:  271 Time(s)

chrisbrown




PostPosted: Mon Jul 02, 2012 2:34 pm   Post subject: Re: Pathifinding

Raknarg, looks like you've implemented a binary tree which, though also awesome, is distinct from - and more complicated than - a linked list.

While a tree node may have zero or more children, a list node may only have up to one. For this reason, a list does not contain any branches and so doesn't adopt the parent-child convention that trees use. Instead, the child pointer is typically called "next" (the next element) or "rest" (the rest of the list).

The last node is usually empty but may point to the beginning of the list; this is called a circularly linked list.

A list may be doubly-linked, where each node has a pointer to its parent, which you've done with your tree node. This is typically called "prev(ious)" and allows the list to be traversed backwards. If you remove one of the children from your node structure, you would have a doubly-linked list.

You can see some visuals here.
Raknarg




PostPosted: Tue Jul 03, 2012 1:39 pm   Post subject: RE:Pathifinding

That was just an example of a linked list application. In the case of evildaddy, I'm fairly certain a tree like mine would be prudent.
Insectoid




PostPosted: Tue Jul 03, 2012 4:57 pm   Post subject: RE:Pathifinding

No, that's an example of a data structure application. A linked list is a linked list, and a tree is a tree. A linked list is pretty much a unary tree.
Raknarg




PostPosted: Wed Jul 04, 2012 11:37 am   Post subject: RE:Pathifinding

Look, that's jis ust a technical difference, the concept is the same thing, Are you telling me a tree is not a linked list? It is a list, that is linked in a tree-like fashion. If you understand any of the concepts, you'd be able to understand them all. I think it would be prudent to put them all under one name.
Display posts from previous:   
   Index -> Programming, Turing -> Turing Submissions
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 23 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: