VB 6.0 - A* Path Finding: Tricks for speed?

[Tontow]

I need some tricks to make my A* path-finding program faster.

At the moment the only trick I use is a Binary heap to find the point with the lowest F score ( F = G + H ).


I was thinking of using a textbox in place of a 2D array because I can only make a 1000x1000 with out getting an error, but there might be a better way?

[leinad31]

A control would be a lot slower. Since you'll access its text property might as well use a string over it... why not keep the array?

[Tontow]

I can't keep the 2D array because I can't make it big enough due to limitations in the maximum size of the array that VB 6.0 can handle - I forget the maximum size that an array can be (I'm having trouble finding it on MSDN), but I do know that its not big enough to accommodate my needs.

I was thinking of using a text box because then I could use HWND (I think) to return the line (x) and the letter (y) and because it’s a textbox, I would have an unlimited sized array. (It is worth noting that I don’t know much about using HWND. )

Is it possible to get instant results from a string or an array?

[Doogle]

I don't think you'll have much success with a TextBox.

The Text setting for a TextBox control is limited to 2048 characters unless the MultiLine property is True, in which case the limit is about 32K.

[leinad31]

Post your code. I can't simulate your problem; I can create 10,000 x 10,000

[Tontow]

The next best thing would be a 1D array which would sort the X values with the Index.
--------------------------------------------
IE: 4,5 4,7 2,1 2,3 3,8 would make an array that looked like
Index - Value
1 - null
2 - 1 3
3- 8
4- 5 7
---------------------------------

But that would still end up being quite slow if multiple Y values ended up being in the same index.

Anyone have some more ideas?

[Tontow]

Post your code. I can't simulate your problem; I can create 10,000 x 10,000

How?

I get an out of memory error with:
Dim myvar(10000, 10000)

edit: That's with a blank project btw.

[westconn1]

dim myvar() as WHAT?
depending on the type memory use can be quite different, if an array can not be big enough to hold your data then maybe you need to write your array out, when the array is full and restart

[Tontow]

As Variant, which is what it defaults to when you don’t specify the type.

I can do a 10,000 x 10,000 with the Integer type, but unfortunately it is still not quite big enough.

[leinad31]

Use a database

[Hack]

Use a database

Agree. Much of the concerns expressed would go away if you simply stored what you needed to store in a database and ran querys against it as needed.

[Tontow]

What is the fastest kind of database and how do I use it?

[leinad31]

I'm thinking of server based databases, e.g. Oracle, SQL server, MySQL, etc? Is this also what your thinking or are you thinking more along the lines of an Access database?

[Tontow]

I really don't know anything about databases (nor have I used them before), so I don't know which would be best to use.

Eventually, this A* path finding algorithm will be used to draw horizontal and vertical lines around and between several images to generate a visual representation of a tech tree for a game called Free Allegiance.

Speed is one of my major issues since there can be upward of 500+ paths that need to be drawn.


What do you recommend I use?



EDIT: I also came across http://www.vbforums.com/showthread.p...ight=big+array .
Would that method be faster than using a database?

[Tontow]

Anyone?

[sessi4ml]

Maybe I don't understand the problem...
'

Dim MyVar(10000, 10000) As Integer
Dim row As Integer
Dim col As Integer
'

Private Sub Form_Load()
        For row = 0 To 10
            For col = 0 To 10
                MyVar(row, col) = row + col
            Next
        Next
        
'
'
For row = 0 To 10
            For col = 0 To 10
                Text1.Text = Text1.Text + Str(MyVar(row, col)) & vbCrLf
            Next
        Next
        
End Sub

[leinad31]

The advantage of server based databases is they support procedural SQL so you can shift processing of data on the database and just have your application get/display the result.

Bad news is you have to learn procedural SQL of particular database in addition to providing db server host machine.

It will help manage the volume of the data but in the end everything boils down to algorithm (are computational shortcuts possible) and hard disk speed.

[Tontow]

Maybe I don't understand the problem...

Problem is that in order to speed the algorithm up a significant amount I need to get rid of about 4 larg loops and use a very larg array; About 1,000,000,000 x 1,000,000,000 . VB 6.0 dosen't have the memory for something that larg, so I need to find workarounds or use a database.

It would be great if it I could find a database that could be used localy.

[LaVolpe]

Awhile back when I was considering the idea of large arrays, one of my concerns was memory & speed also. Researching the Internet provided some possible solutions: use A* on a scaled basis and using heirarchal methods were a couple that caught my attention. Research requried.

I don't think this will apply, but you can see a different approach I took; it does not adapt well to games however.

[Tontow]

Awhile back when I was considering the idea of large arrays, one of my concerns was memory & speed also. Researching the Internet provided some possible solutions: use A* on a scaled basis and using heirarchal methods were a couple that caught my attention. Research requried.

I don't think this will apply, but you can see a different approach I took; it does not adapt well to games however.

Could that method be adapted to be restricted to vertical and horizontal movement? With so many lines to be drawn, vertical and horizontal movement may look a little cleaner.

[LaVolpe]

No. However, the points returned and lines between those points can be adapted to determine which "tiles" the path crosses. I stress that though it can be used for a quick route for very large gameboards, it is not truly designed to be used as the correct route. That project I created was not intended to replace A* in games; that project does not take into consideration directional paths (i.e., one-way streets) nor does it consider weighting (sand, slopes, etc).

[Tontow]

While that is a very nice method, I'm not going to be using my algorithm for a game board; I will be using it to generate game documentation.

The game can be found at: http://www.freeallegiance.org .
Users create large Cores (think custom game files) that have several races and allot of tech and several ships; while there are programs available to explore the tech trees of these Cores, there are only 2 that display the tech trees visually (neither of which are perfect, yet).
One of them is quite nice except for the wide spacing between tech and the hand full of bugs.
The other is mine, but the straight lines make it look messy. (This algorithm is going to be used to fix that.)

[leinad31]

One way to speed up processing is to design properly the data representation... what have you done so far in this respect and in consideration of row-column format or normalization of tables?

[Tontow]

Here is what I have so far in my attempt at creating tech tree documentation: http://www.geocities.com/tontow_merlin/ .

I have given the user the ability to move the images around to fine tune the final look. At the moment the alignment is a tad on the messy side - I intend to clean that up next after I get this path finding part done.


But we are getting a little off track.

What would be better/faster? An array that is stored on the hard drive as demonstrated in http://www.vbforums.com/showthread.p...ight=big+array ,
OR
A database (preferably a local one)? (Please suggest one if your answer is a database.)

[leinad31]

If it will be a local database then you wouldn't get much advantage with using a database (no stored procedure, no parallel execution or bulk processing of query and other database performance enhancements), it will only allow storage of large volume of data.

Try making a prototype first of the large array stored on hard drive... you may still run into overflow issues since you will be limited to range supported by relevant data type used to hold index/array size, pointer value, or other similar issues.

[Tontow]

Sorry for the broaken link, here is the correct one.
An array that is stored on the hard drive:
http://www.vbforums.com/showthread.p...ht=fill+string

At the end it has a link to the code base vershion of it.

[Tontow]

@LaVolpe

With your method. How did you determin weather or not a line between points was invalid?

[LaVolpe]

My method (post #19 above?) only borrows part of A*. My method is used on open graphs, non-tiled, where literally every pixel can be considered a tile and had to process millions of pixels. With my method, groups of pixels were consolidated into obstacles, as rectangles, and all the other millions of pixels were open spaces that were also consolidated into rectangles. Whenever a path would attempt to cross into/over an obstacle it was invalid.

The reason my method could process millions of pixels (1x1 tiles) was because of the rectangles. Any rectangle uses 16 bytes of memory; and let's say the rectangle was 20x100, it encompasses 2000 pixels. 16 bytes can be handled faster/more efficiently than 2000 bytes. But the purpose of what I developed it for was not gaming; it was logic used for graphing networks, circuits, and hardware. The path finding was used to build/display the circuits between objects on a graph, where the graph could literally be several screen widths by several screen heights.

[Tontow]

Whenever a path would attempt to cross into/over an obstacle it was invalid.

How did you determine when a path would attempt to cross into/over an obstacle?

I need the answer to a math problem.
The only obstacles I have are rectangles (images, but still rectangles). A rectangle is made up of 4 lines. Is there a formula that can tell me weather or not a 5th line intersects any of the 4 lines?

[LaVolpe]

Are you using A*? And are you using tiles? If so, your obstacle tiles should be identified with a property that it is an obstacle & more advanced games would have other properties too to indicate whether moving thru the tile would be faster (downhill for example), slower (uphill or swampy), maybe whether the tile is one way or bidirectional, and many other properties specifically for that game. A* moves from one tile to the next, using guessing/heuristics, and keeps track of best/worse move combinations, and can prevent exploring any tile more than once which is one of its strongest features. Recommend reading some more about A*, maybe looking at the games section of this forum for any posts that use it, PSC, and gamedev.net. Note about last link; apparently gamedev.net is down temporarily for patches as of this posting.

[Tontow]

Yes, I have read that already.

But what I was planning on doing was using a large grid and then shrinking down to a smaller grid when I got closer to the goal. - (Will swich to a smaller grid when the destanation is between points.)
I want to discourage the paths from crossing each other and also keep them from crossing over images.

Thing is, I cant seem to recall how to mathematically tell weather or not 2 lines (lines and not rays) intercept one another.

[LaVolpe]

Thing is, I cant seem to recall how to mathematically tell weather or not 2 lines (lines and not rays) intercept one another.

I have to take off now, but wanted to leave you with this quick idea. Search this forum for: Line Intersection. Not that many hits & I think you will find what you are looking for.

[leinad31]

Yes, I have read that already.

But what I was planning on doing was using a large grid and then shrinking down to a smaller grid when I got closer to the goal. - (Will swich to a smaller grid when the destanation is between points.)
I want to discourage the paths from crossing each other and also keep them from crossing over images.

Thing is, I cant seem to recall how to mathematically tell weather or not 2 lines (lines and not rays) intercept one another.

How about a pre-defined layout (complete path) which shrinks or adjusts to fill in spaces in the same way you'd remove rows or columns in excel that are blank. You wouldn't have to worry about intersection then since your just shortening existing lines and moving images accordingly. Distance calculation is also simplified cause its predefined. Image positioning is also facilitated since you just move to blank cell whose position is already predefined.

[sessi4ml]

How about if the data base is removed?
Open file as random len=16...?

[Tontow]

How about if the data base is removed?
Open file as random len=16...?

??
To what are you refering too? (Do you have the right thread?)