Gil* Pathfinding

[TribulationStaff]

Well, I figure I might as well give this a go. This is much faster than soul's at this point. Taking no more than 10 seconds. This NPC is not a cart of premade code, nor a redo of Soul's. I made this from scratch based upon the description of the process.

Now, as you may or may not know, I don't just show off finished scripts, I like to leave bugs in so that other people don't just slap it onto their playerworld. In this case, I think that there is a slight overflow problem with the string arrays, as they do get rather full rather fast. If Stefan wanted to double or more the array caps, I believe it would make it a more useful script. However, I am not about to let onto my plans for cleaning it up.

Without futher ado, the level.

[Dach]

hehe, nice name, pretty easy to make it freeze up Graal though, no?

[TribulationStaff]

Read the caveat in my original post dude

[Projectshifter]

Not bad =)
I will take a closer look later, seems to work pretty good. Only one big flaw I saw, if it's not possible to get to that location, it locks up the game =p
---Shifter

[SaijinGohan]

The Bam should be SHAZAM! Anyways, thats pretty awesome.

[Questa]

That's really cool, you should add a failsafe so that if you can't get to the X then the guy says so. Otherwise it just freezes.

[Snakeandy7]

Lol, add more bushes > graal crash !

[TribulationStaff]

Graal does not have a whole lot of computing power, unfortunately.

[wonderboysp2p]

he didnt like my maze i made for him

[marcoR]

he's a very selfish NPC.

[Falados]

I dont think it is very cost-effective to impliment an A* algorithm for pathfinding via scripts. Never-the-less, good work.

[CheeToS2]

I added a couple more tiles.. its been way more than 10 secs so far, hes still "thinking" and graal is in a nicely frozen state.

[TribulationStaff]

Agreed, A* is just too powerful for Graal's engine. However, this is the first scripting challenge I have had in a while. Not many things force me to go out and learn new skills.

As for the path, it isn't exactly the length of the path, its the complexity. When it gets too complex, then it overloads Graal, but it can easily go cross screen if it doesn't need to do anyything tricky

[superb]

Originally posted by TribulationStaff
Agreed, A* is just too powerful for Graal's engine. However, this is the first scripting challenge I have had in a while. Not many things force me to go out and learn new skills.

As for the path, it isn't exactly the length of the path, its the complexity. When it gets too complex, then it overloads Graal, but it can easily go cross screen if it doesn't need to do anyything tricky

Yeah and what's strange is graal often will take 100% of the cpu time. Stefan should really focus on optimization in the C++ rewrite if he hasn't been already.

[Falados]

Originally posted by superb


Yeah and what's strange is graal often will take 100% of the cpu time. Stefan should really focus on optimization in the C++ rewrite if he hasn't been already.

you forget, graal isnt like window message-based apps that wait untill it gets input from the user.. it is constantly updating the game state regaurdless of user input. Thats how games are. I'm sure you'll find that most, if not all, games that you play will take up ~99% of the CPU time.

[Dach]

Mleh, the only real problem with A* in Graal is the amount of script needed to run it properly. You can easily reduce cpu time by making it multi level (check larger areas first then small areas inbetween) , well that and it's overkill...

[TribulationStaff]

The amount of script? Mine is like 2 pages tops.

[adam]

What would be nice is this, a built in really really fast function that returns an array of nodes to goto to get somewhere.

FindPath(startx,starty,endx,endy,width,height);
Pathx = {x,x,x,x,x,x,x,x,x,x,x}
Pathy = {y,y,y,y,y,y,y,y,y,y,y}


But... yeah like that will happen?

[wonderboysp2p]

i read that 3 times and i just figured out what you meant... heh yea that would be nice

[TribulationStaff]

it would bet better for it to return

pathcoords={x,y,x,y,x,y}

[konidias]

Originally posted by TribulationStaff
Well, I figure I might as well give this a go. This is much faster than soul's at this point. Taking no more than 10 seconds. This NPC is not a cart of premade code, nor a redo of Soul's. I made this from scratch based upon the description of the process.

Now, as you may or may not know, I don't just show off finished scripts, I like to leave bugs in so that other people don't just slap it onto their playerworld. In this case, I think that there is a slight overflow problem with the string arrays, as they do get rather full rather fast. If Stefan wanted to double or more the array caps, I believe it would make it a more useful script. However, I am not about to let onto my plans for cleaning it up.

Without futher ado, the level.

"This is much faster than soul's at this point. Taking no more than 10 seconds."

Lol, what? I put one bush down and it locks up Graal. How is that faster? You can barely have it find it's target if you change the position of anything in the level. That's not pathfinding, I can make a crappy npc that can walk from point a to point b with a predefined tile maze.

"I don't just show off finished scripts, I like to leave bugs in so that other people don't just slap it onto their playerworld"

Is it that you don't want to show off finished scripts, or is it that you can't finish it? I mean really, this is far from "a little buggy". It barely works at all, heh. At least SB's didn't lock up Graal, it just took a long time.

[TribulationStaff]

It works, it just smokes Graal's proverbial wheels. Keeping in mind there are like 4000 some tiles on a level, I am not sure Graal's engine can handle arrays or lists that long.

Also, it was uncalled for to insinuate that I am incapable of improving the script. It would have been more appropriate to give a constructive challenge.

[konidias]

Originally posted by TribulationStaff
It works, it just smokes Graal's proverbial wheels. Keeping in mind there are like 4000 some tiles on a level, I am not sure Graal's engine can handle arrays or lists that long.

Also, it was uncalled for to insinuate that I am incapable of improving the script. It would have been more appropriate to give a constructive challenge.

Then make a better working version? I don't understand why you're even going to post a script if it barely works. Nobody can take it and use it because they'd have to do major rescripting to it, so there is no point in even going by what you've given, they might as well start from scratch.

I just don't get why you'd need to post a pathfinding npc after Soulblade, that is less efficient. But if that's not bad enough, you go beyond that and say that it's more efficient? It doesn't make sense to me. Sorry.

[TribulationStaff]

I just don't get why you'd need to post a pathfinding npc after Soulblade, that is less efficient. But if that's not bad enough, you go beyond that and say that it's more efficient? It doesn't make sense to me. Sorry.

Please do not misrepresent my statements. Faster is not more efficient. The topic intrigued me so I wanted to give it a go myself.

Then make a better working version? I don't understand why you're even going to post a script if it barely works. Nobody can take it and use it because they'd have to do major rescripting to it, so there is no point in even going by what you've given, they might as well start from scratch.

Firstly, that is the whole point. Soul's is no more usable as is than mine. His problem is speed, my problem is, I believe, overflow. Don't criticise me for doing it second, congratulate me for doing it at all. This forum isn't about competition, this forum is about developing our scripting skills. I think Soul, or anyone else who does pathfinding in the future, would agree with me on this: teaching myself A* will help my scripts yet to come.

[konidias]

Originally posted by TribulationStaff
Please do not misrepresent my statements. Faster is not more efficient. The topic intrigued me so I wanted to give it a go myself.

Firstly, that is the whole point. Soul's is no more usable as is than mine. His problem is speed, my problem is, I believe, overflow. Don't criticise me for doing it second, congratulate me for doing it at all. This forum isn't about competition, this forum is about developing our scripting skills. I think Soul, or anyone else who does pathfinding in the future, would agree with me on this: teaching myself A* will help my scripts yet to come.

But his works... How is yours faster? Like I said in the pm I sent, it would be like two car companies making the fastest car, and one company saying "well ours could go faster, but it would explode".

You are the one that compared the scripts pal. I'm not attempting to criticize you for doing it second, I'm doing it because you're doing it second and saying yours is faster than the first.

[Judge_S]

Originally posted by konidias
Nobody can take it and use it because they'd have to do major rescripting to it, so there is no point in even going by what you've given, they might as well start from scratch.

I believe sir, that is the whole point of it acting as it does, from the script here on the forums.

[SaijinGohan]

Originally posted by TribulationStaff
.....Keeping in mind there are like 4000 some tiles on a level.....

Close. There are 4096 is a level.

[TribulationStaff]

Actually, its more like this: One car company that says, ok our car always goes 5 mph. The other car company says, our car goes 60 mph, but if you drive it more than a block, the engine will overheat because we didn't add a cooling system.

[Dach]

Originally posted by TribulationStaff
there are like 4000 some tiles on a level

You don't have to check all of them, just the ones you might use...

[TribulationStaff]

Well, the path search spreads out pretty fast, especially when you have to go away from the target a little bit to get to it. Upon more playing with the code, it may not be an overload issue. It may be that my code to go back from a dead end and start again is flawed.

[adam]

Originally posted by TribulationStaff
Well, the path search spreads out pretty fast, especially when you have to go away from the target a little bit to get to it. Upon more playing with the code, it may not be an overload issue. It may be that my code to go back from a dead end and start again is flawed.

Yeah, when I tried my hand at it that was one of the problems I ran into.

[Kaimetsu]

Originally posted by TribulationStaff
I think that there is a slight overflow problem with the string arrays

Why oh why oh why oh why oh why are you using string arrays?

[TribulationStaff]

Because it makes things much easier. In particular, maintaining the open, closed, and path lists.

[Kaimetsu]

-_-

When did efficiency stop meaning something?

[TribulationStaff]

Probably when I started coding. I mean, mathematicians are the ones who invented proof by contradiction. With PBC, you have no idea where you end up

Seriously though, what is inefficient about string arrays?

[Kaimetsu]

Originally posted by TribulationStaff
Seriously though, what is inefficient about string arrays?

@_@

1) Larger storage costs - pure binary numeric representations are more size-efficient than ASCII conversions.
2) Every time you want to do any kind of operation on the members or store new values, you need to convert from number to string or vice versa.

[adam]

Originally posted by TribulationStaff
Because it makes things much easier. In particular, maintaining the open, closed, and path lists.

I don't know why I didn't notice before.


Kaimetsu is right man.

It's far far better to try to make using regular arrays work.

[Dach]

Mleh, it's alot easier to have a sorted open list, and to not add walls to it in the first place. Because even if you come across a dead-end, the script will just jump to the next best tile without missing a beat.

*to self* Hey, my script is atleast twice aslong as any of the other ones! crappers...

[adam]

Originally posted by Dach
Mleh, it's alot easier to have a sorted open list, and to not add walls to it in the first place. Because even if you come across a dead-end, the script will just jump to the next best tile without missing a beat.

*to self* Hey, my script is atleast twice aslong as any of the other ones! crappers...

As long as it worked good, it's a good start.

Could think up some nice techniques to reduce code length maybe.

[Dach]

well really most of it's length is due to the fact that I used functions (more returns), and anything I change to it will just be adding more code (multi-level pathing stuff) which will just make it work faster if done correctly