Re: Shortest path related - Algorithms Discussion Boards

"why do you only know adjacent squares...?"

Why do you wan't to change my problem?
Thats the problem.. don't try to help me solving another problem :P

when
1. you know the state of the 8 squares adjacent to your current position;
2. and you can move around;
3. and you have sufficient memory and time to discover and record;

then you can scan the whole area, and in the end you know the state of the whole area.
And before you have finished that, you also have found the destination cell.

Or am I missing something here?

Confused | :confused:

Luc Pattyn

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

Yes but by moving all around you are not doing the shortest or almost-shortest path to the goal

Sorry if I explained bad.. the objetive is to found the goal in a short path.. maybe no the shortest, but of course not the largest (by movin all around)

Luc,

My thoughts exactly. You have to know at least the matrix bounds to do a search. See my thoughts in the three posts below (and in the several above). At least it would be a way to find the path knowing only the adjacent 8 cells, BUT, you need to know either the matrix bounds, or the fact that any barrier lies entirely inside the matrix so you do not step outside of the matrix and you are just stepping around the end of the barrier (the barrier inside of the matrix assumes that the direction to the goal from the current location is known - in this case the matrix bounds need not be known and will work without even knowing what the starting, current, or goal location is, but someone, somewhere needs to know the current position and the goal position in at least relative terms to calculate the direction to the goal from the current position). I even covered the case where the direction was not known, but in that case the matrix bounds must be known to do an exhaustive search. In all cases, some thing needs to know in what way the goal is identified to know when you are done, and also what a barrier looks like in the 8 adjacent cells. Something something needs to know how to move around to go from one cell to another.

Dave.

yep. the problem setting is far from complete. it is even unclear what is meant by shortest path:
- least amount of calculations? or memory?
- least amount of travel (discovery+solution)?
- shortest path after all required area has been visited?

and what is path length? number of steps? what with diagonal steps? number of turns?

Smile | :)

Luc Pattyn

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

I played around with this many years ago on my NEC APC. I had a matrix of moves for each intersection (think of the path to the next location as a road, and the location having 4 directions to go), each element of the move matrix was a byte, the high nibble had 4 bits indicating the entry direction (for backtracking), the low nibble had 4 bits indicating which directions had been tried. When a direction was tried (when you started to go that direction) you set a bit in the low nibble for the selected direction, and set the bit in the high nibble for the entry direction, and if the move was valid you continued. If this was a barrier or if you had already visited this intersection (some bit set in either high or low nibble, then you backtrack to the first intersection which had some available path and tried a different direction. If you backtrack FROM an intersection, then reset the bit in the high nibble of the intersection you are returning FROM but not the bit in the low nibble you are returning TO. You need to check the original matrix to see if the location is a barrier or if you have found the target.

Note: You do not want to visit an intersection more than once, not to cross (from east to west, crossing a north to south path), not to touch (east to north where there was a path from west to south), and not to follow a prior path (huge loop).

To find the shortest path (maybe more than one the same length), try all paths from the starting point and save the path intersections you visit (deleting the last intersection point for each backtrack) until you find the target. The length of that one path is then known. Continue the searches until all directions from the starting point have been tried.

To find the longest path, modify the test for visiting an intersection to allow either a touch, and/or a cross, and try all paths and select the longest.

I played around with depth first searches (described above), then breadth first searches (harder to implement). Fun exercise!

Dave.

Sorry for the double post, but you did mention that you have all 8 points available. The same method can still be used, but use a WORD matrix and keep 8 bits in the high BYTE and 8 bits in the low BYTE - the same algo, just more possibilities.

When saving the paths, label the locations as single letters (A-Z) for both the rows and columns (giving a 26x26 matrix) and thus a two letter location name, or use double letters for (26X26)x(26X26) and thus a four letter location name, or triple letters ... (how nasty do you want to get)

Dave.

I just thought of a simpler way to log the paths - use a character 0-7 to log the outbound direction from the current location. The path starts at the specified location, thus is unique, and the string length is the length of the path. Note: The maximum string length could be (for an X by Y matrix) (max(((x/2)*y), (x*(y/2)))+1) to allow for snaking around barriers.

To avoid special checks at the edges, simply border the matrix with a barrier (on the top, bottom, left, and right) which has to be checked for anyway, even in interior locations (the edge barriers would have to be included in the matrix sizes). If you joined the left to the right you would have a cylinder, and if you also joined top to bottom, you would have a torus and would not have a need for the barriers at those joined edges - there would be no edges at the joints.

The calculations for indexing between locations could easily be done with table lookup to get two decrementers/incrementers (-1, 0, or +1), one for east west and another for north south, the table indexed by the direction (0 for north - decrement north south, no change for east west, 1 for north-east - decrement both north south and east west, etc. To handle the cylinder or torus situation, the current location would be incremented/decremented, then the resulting value used to index another array (assume a matrix of 10x10, this new array would be: (9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0). If x and y were different, then two arrays would be needed, one to adjust x another to adjust y. With table lookup, no complicated edge checking is needed. The only checking would be to see what direction to check next, and that could also be done with a 256 element lookup table (i.e. for a direction byte with bit 0 reset, go north, for bit 1 reset go NE, for bit 2 reset go east, etc).

Both the matrix and the movement matrix could be combined into one DWORD matrix with the upper WORD for the location specifier (simple location, start location, target location, barrier location), and the lower WORD the two direction BYTES.

One speedup would be to check the entire array for barrier locations, and set the corresponding bits in all of the 8 locations adjacent to each barrier location so that it would appear that the path had already tried to go that way. With edge barriers, two solutions are available. First, do edge checking for the edge barriers, then no further edge checking needed. Second, add an extra column outside of all edges, then no edge checking need be done (you would be setting bits in columns/rows that would never be examined), but the matrix is 4 columns/rows bigger.

If you have any questions, just ask.

Dave.

I have a Red Black Tree in which is stored some 'sparse' keys. I might have e.g. {1, 11, 22, 31, 47, 63, 71} etc. The pattern is not important just the sparseness of keys.

What I would like to do is look up the 'closest without going over' key from my BST, which is in-fact the index into a very large array (>10M elements).

So for example if I'm looking for entry 55 using the above index, I would like to return the data stored at the node for 47, which is the best guess index for me to start searching my array for entry 55.

It sounds simple enough but I can't find code or even an algorithm outline anywhere. The closest thing I've seen involves searching for a range of values, but if I knew the range I'd need, I wouldn't need this index in the first place... more behind the scenes, know what I mean? Smile | :)

Couple of things:
* I don't know the indexes or the gaps between keys beforehand.
* This index is rebuilt very often (after array cut-paste operations).

In other words any 'workaround' solutions that don't directly answer my question need to be general enough and fast enough to deal with the problem. The index actually loses information as the array shrinks but the original indexes must be kept.

Hope I've made the problem simple and clear enough. Any help will be very much appreciated!

To find the closest without going over, look for the key until you get down to a leaf node.

If the leaf contains your key you're done. If the leaf is less than your key, you're done in this case too. If the leaf is over your key, go to the next lowest node. (There's a simple algorithm for doing this in a binary tree, that you can find in an algorithms book. I don't recall it off the top of my head.)

BTW, I used to use red-black trees too to keep them balanced. Then I found out about Scapegoat Trees (http://en.wikipedia.org/wiki/Scapegoat_tree[^]) which stay balanced WITHOUT the overhead of a red/black bit in each node.

Have you considered using a b+ tree instead of a red black tree for the base indexing. Whenever you find a leaf key that is too big, the next smaller key is immediately before it, or else is the last key of the preceding block, both of which are easily, quickly accessed without traversing tree nodes. I specifically refer to the B++ tree implementation of CBTREE from Mix Software in its C Database Toolchest.

Dave.

Molecular Mechanics?

in C# just use a Dictionary with key/location as your lookup method.. simple...

It would be something like see this see also

new Dictionary< int Value,int Location>

then when you move something you can (i don't remember specifics) eitheer change the dictionary value or add/remove.. etc..

Thanks for all the suggestions. I'll look at these over the weekend and decide which ones I can implement easily and which of those performs as required.

Have a great weekend and thanks again.

On Pixar's How We Do It[^] page (slide 13), they talk about what goes into each frame of a movie. Maybe I'm just being dense, but...

Let's assume the average movie is 90 minutes, or 5,400 seconds, long.
Each frame is 1/24 of a second, so there are 129,600 frames.
If each frame takes about 6 hours to render, that would be 777,600 hours.

They undoubtedly have some serious horsepower doing this rendering, so is that 777,600 computer hours?

"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

I am sure that are CPU time measurements.
Calculate it into years, then you will see. Smile | :)

However they must have amazing Pcs.

Cheers

You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)

Fatbuddha 1 wrote:
Calculate it into years, then you will see.

I did, hence the confusion.

"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

I suspect a large degree of parallelism in use.

A very very very big cluster Smile | :)

.
And then several of them Smile | :)

.

Have a nice weekend
cheers

You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)

Or it could be "actual time"; they didn't say much about the granularity of their parallelism, maybe they render multiple frames in parallel, instead of multiple pixels?
I didn't read the whole "How We Do It" though

My guess is that you would find they are rendering in layers and then integrating the layers. This would allow them to render smaller areas of a frame in less time.

For example, you can render a background once and then render foreground characters that are smaller sections of a frame and thus render in less time, and then integrate them together.

I don't think you could do it all this way simply because of how the various parts of a frame may interact, but I think this could get you a better (smaller) time.

LinkedIn[^] | Blog[^] | Twitter[^]

That's only 89 CPU years. Even with 180 computers, that's 6 months of rendering and they have much larger rendering farms.

You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.

They Have "LARGE" render farms... LARGE.

they can "cut corners" in some aspects of the Render procedurally.

they can layer and post process.. usually this is what they do however this causes the large "finish rendering" time because someone goes in and digitally touches up the shadow, or adjusts the intensity of the red in the fire in the background etc...

all the photo-realistic portraits that i've seen can usually be rendered in under a couple of hours(very detailed) but being the perfectionists that they are the artists like to go back in and tweek the resulting image, make the gem more sparkely, the drool wetter.. etc.

Yeah, that sounds right - even if a little on the 'light' side by today's standards.

Apparently, Pixar used about 1000 Sun UltraSPARC servers to do the original ToyStory. When they did the movie CARS, they used about 300 times the processing power. OMG | :OMG:

Tom Duff tells us that they're looking at around 1.2 million cpu hours for a 1.5 hour movie.....

Here's where you can find some more facts and figures: real-time-toy-story-3d[^]

Thanks for that link.

"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

Anyone know about travel or comparison algorithm for n-ary tree.please help me.. Confused | :confused: