8 Replies - 418 Views - Last Post: 07 January 2014 - 06:34 PM Rate Topic: -----

#1 BerkayD  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 28-December 13

Path Finding

Posted 04 January 2014 - 12:34 PM

Hi, I have a question about path finding systems. Well, i am developing in XNA, but its not a XNA specific question so i am asking in here.

Well, first to mention. I have a character in game. But i don't want to "just" control it with keyboard. I want to use a "click/hold to move" system. So i need to use path finding system to make my character move to the clicked point in right direction.

Well, i have searched some of the path finding algortihms. Like A* and Dijkstra's algorithm. And they are working in nodes. So, what that means is, i have to build a node system to my game. Seperate the game in to squares. So, if a character moves in the path finding system, his moves won't me smooth. He will move by jumping in nodes 1 by 1. So that won't look smooth in the game. If i want to move it more smoother, i have to make those nodes smaller. So i have to seperate more and more until its smooth enough. But my concern is. If i use more nodes, the algortihm, the process will be slower. So i am asking about your opinion. What should i do ?

About my sprite. I am using a 8-direction sprite. I mean my character turns his face in 8 direction. I programmed it. The character can easily face through the point. There is no problem with that.

Ohh, by the way. I can give an example about the system i want. Well, basicly diablo 1's path finding and movement system is the exactly the one i am trying to program. They also used 8-direction sprite in game. This is the exactly the one i want to make. Here is a video link. Take a look at the first 10 seconds. Its more than enough. http://www.youtube.c...h?v=Fl5I5CUTqh4

Is This A Good Question/Topic? 0
  • +

Replies To: Path Finding

#2 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8915
  • View blog
  • Posts: 33,430
  • Joined: 12-June 08

Re: Path Finding

Posted 04 January 2014 - 12:51 PM

You could throw down a 'navigation mesh' and see how that works.

https://developer.va...vigation_Meshes
http://www.ai-blog.n...ves/000152.html
Was This Post Helpful? 0
  • +
  • -

#3 BerkayD  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 28-December 13

Re: Path Finding

Posted 04 January 2014 - 01:22 PM

Well thanks for reply, i am reading these. But as it seems, it just explains the navigation meshes. There must be more algortihms beneath these. Also i don't know if it differs but they are on 3D games. I am making 2D game. What i need is more basic path finding system that works efficient. As i said in my first message. I need exactly the one in the diablo 1. That game uses the exact system i want.
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8915
  • View blog
  • Posts: 33,430
  • Joined: 12-June 08

Re: Path Finding

Posted 04 January 2014 - 01:28 PM

I would imagine there is one.. I am not going to do all the research for you.

As for your search for diablo1 pathfinding.. I am unclear what the issue is. If the movement is not smooth then tweak your code for it. A* is just a method to search efficiently, right? If you have the current PC's location and the mouse click your code should pullup viable paths to there and the A* would be used to determine the best/fastets/etc way.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10366
  • View blog
  • Posts: 38,403
  • Joined: 27-December 08

Re: Path Finding

Posted 04 January 2014 - 01:36 PM

Quote

But my concern is. If i use more nodes, the algortihm, the process will be slower.

Sure, more nodes means more steps. Both algorithms run in polynomial time though. It's not going to be appreciably slower to run either algorithm on more nodes.
Was This Post Helpful? 0
  • +
  • -

#6 BerkayD  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 28-December 13

Re: Path Finding

Posted 04 January 2014 - 01:51 PM

View Postmacosxnerd101, on 04 January 2014 - 01:36 PM, said:

Quote

But my concern is. If i use more nodes, the algortihm, the process will be slower.

Sure, more nodes means more steps. Both algorithms run in polynomial time though. It's not going to be appreciably slower to run either algorithm on more nodes.


Ohh, that was the answer i needed to. Thanks. Okay what if i use pixel size for nodes? I mean, if i define the node as a pixel. Would it be noticeably slower ?
Was This Post Helpful? 0
  • +
  • -

#7 axel1994  Icon User is offline

  • D.I.C Head

Reputation: 83
  • View blog
  • Posts: 167
  • Joined: 27-May 13

Re: Path Finding

Posted 04 January 2014 - 01:59 PM

If you have 2 nodes, then you don't necessarily have to teleport your character from node 1 to node 2.
If you want to move from node 1 to node 2. Just move in a straight line, but do the movement in multiple frames
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10366
  • View blog
  • Posts: 38,403
  • Joined: 27-December 08

Re: Path Finding

Posted 04 January 2014 - 02:10 PM

Quote

Ohh, that was the answer i needed to. Thanks. Okay what if i use pixel size for nodes? I mean, if i define the node as a pixel. Would it be noticeably slower ?

Give it a try. Personally, I feel that's overkill.
Was This Post Helpful? 0
  • +
  • -

#9 omega14  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 4
  • Joined: 13-December 13

Re: Path Finding

Posted 07 January 2014 - 06:34 PM

Why don't just have the computer make 2d navigation mesh that in the form of a grid.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1