Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 121 122 [123] 124 125 ... 796

Author Topic: if self.isCoder(): post() #Programming Thread  (Read 902589 times)

malloc

  • Bay Watcher
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1830 on: February 29, 2012, 07:09:58 pm »

I see what you guys mean now. Yeah, I guess it makes sense that you loose out on a lot by taking these 3+ years out of my working life. But the situation is quite a bit different here, it's hard to get anywhere without a education.
Logged

MaximumZero

  • Bay Watcher
  • Stare into the abyss.
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1831 on: February 29, 2012, 07:14:07 pm »

I know that here, a "2 year degree" (which takes 3+ years,) is mandatory, if you want a job doing anything touching computers. After this, I'll probably be a junior code monkey for the next 3-5 years while working on a Bachelor's. Then I might be able to call myself a professional programmer. Maybe.
Logged
  
Holy crap, why did I not start watching One Punch Man earlier? This is the best thing.
probably figured an autobiography wouldn't be interesting

Willfor

  • Bay Watcher
  • The great magmaman adventurer. I do it for hugs.
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1832 on: February 29, 2012, 07:35:52 pm »

Being a form of engineering, the following applies to programming too:
"When told that work is work and spare time is not for engineering I am concerned that the candidate's world view is not really that of a successful engineer."
http://www.analog.com/en/all-operational-amplifiers-op-amps/operational-amplifiers-op-amps/products/raq_make_do_issue61/resources/faq.html
Being in the process of an education in audio engineering, I'm extremely grateful for this link.
Logged
In the wells of livestock vans with shells and garden sands /
Iron mixed with oxygen as per the laws of chemistry and chance /
A shape was roughly human, it was only roughly human /
Apparition eyes / Apparition eyes / Knock, apparition, knock / Eyes, apparition eyes /

Mego

  • Bay Watcher
  • [PREFSTRING:MADNESS]
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1833 on: February 29, 2012, 08:10:25 pm »

You know what...I'll probably just write a tutorial on writing makefiles...they're incredibly useful when you have more than three or four files to compile together.

Requesting this. Makefiles are the kind of magic I never really got good at. Probably because I'm not too great at bash scripting.

dreadmullet

  • Bay Watcher
  • Inadequate Comedian
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1834 on: February 29, 2012, 08:40:17 pm »

Here's an animation I made that shows my pathfinding algorithm at work. It's standard A*, which I believe is exactly the algorithm Dwarf Fortress uses. It runs on a seperate thread, too. Take that Toady One!

Spoiler (click to show/hide)
Logged

Willfor

  • Bay Watcher
  • The great magmaman adventurer. I do it for hugs.
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1835 on: February 29, 2012, 08:43:46 pm »

Take that Toady One!
Exactly how many map data variables are being accessed and changed by other processes while your pathfinding algorithm is running?
Logged
In the wells of livestock vans with shells and garden sands /
Iron mixed with oxygen as per the laws of chemistry and chance /
A shape was roughly human, it was only roughly human /
Apparition eyes / Apparition eyes / Knock, apparition, knock / Eyes, apparition eyes /

dreadmullet

  • Bay Watcher
  • Inadequate Comedian
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1836 on: February 29, 2012, 09:01:45 pm »

It's all concurrent. I don't see how that's a problem, though. The worst that can happen is it tries to path past a very recently locked door or something, then realize it's locked when it periodically checks if the path is still valid. I would love to be proven wrong.

It's all very simple at the moment. I understand that Dwarf Fortress is many times more complex than my current engine. I just think it's fun to compare myself to the toad.
Logged

Valid_Dark

  • Bay Watcher
  • If you wont let me Dream, I wont let you sleep.
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1837 on: February 29, 2012, 09:03:48 pm »

Here's an animation I made that shows my pathfinding algorithm at work. It's standard A*, which I believe is exactly the algorithm Dwarf Fortress uses. It runs on a seperate thread, too. Take that Toady One!

Spoiler (click to show/hide)

I've never done any work with pathfinding, and I found this interesting,  Is this really the basic background of a pathfinder?  I expected something a bit cleaner or without so much unneeded work being done,  I can understand basically whats going on here, and I never attempted to think of a way of doing it myself, it just seems like a lot more than I would have thought.
Logged
There are 10 types of people in this world. Those that understand binary and those that don't


Quote
My milkshake brings all the criminals to justice.

MorleyDev

  • Bay Watcher
  • "It is not enough for it to just work."
    • View Profile
    • MorleyDev
Re: if self.isCoder(): post() #Programming Thread
« Reply #1838 on: February 29, 2012, 11:45:14 pm »

I've never done any work with pathfinding, and I found this interesting,  Is this really the basic background of a pathfinder?  I expected something a bit cleaner or without so much unneeded work being done,  I can understand basically whats going on here, and I never attempted to think of a way of doing it myself, it just seems like a lot more than I would have thought.

This is a pretty standard flat implementation of A*. They may be optimisations in certain situations that can be made, but they usually require either the graph being optimised for them or certain assumptions be made. For example, you could treat the overall room structure as a graph and use A* to find your way from room to room, and then use A* again to find your way through each room.

A* is rather efficient as far as path finding goes. It's based on Dijkstra's Algorithm, which checks every node in the graph but is guaranteed to return the shortest path. A* on the other hand, is guaranteed to return a path. It won't always return the shortest path, but the path it returns is reasonably decent and it's faster than Dijkstra's as it doesn't check every node.

You might be able to optimise DF by making it detect 'rooms' as they are made, and then use them for path-finding.

As for threading, DF may be better optimised in terms of concurrency by spreading the search across all the cores. That's usually the easier, less optimal, way of shoe-horning concurrency into a project not designed for it.
« Last Edit: February 29, 2012, 11:49:07 pm by MorleyDev »
Logged

Nadaka

  • Bay Watcher
    • View Profile
    • http://www.nadaka.us
Re: if self.isCoder(): post() #Programming Thread
« Reply #1839 on: February 29, 2012, 11:53:34 pm »

Here's an animation I made that shows my pathfinding algorithm at work. It's standard A*, which I believe is exactly the algorithm Dwarf Fortress uses. It runs on a seperate thread, too. Take that Toady One!

Spoiler (click to show/hide)

It is possible that your seeking algorithm isn't as efficient as it could be. I note that it only seeks in the 8 cardinal directions towards the destination. If it encounters a partial obstruction, but can still move in a direction that places it closer to the destination it might save quite a bit of searching under most use cases.

Code: [Select]
XXXXXXXXXXXXXXXX
X          B   X
XXXXXXXXXXXXXX X
X   .          X
X  .           X
X .            X
XA             X
XXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXX
X          B   X
XXXXXXXXXXXXXX X
X   ........   X
X  .           X
X .            X
XA             X
XXXXXXXXXXXXXXXX
Logged
Take me out to the black, tell them I ain't comin' back...
I don't care cause I'm still free, you can't take the sky from me...

I turned myself into a monster, to fight against the monsters of the world.

Valid_Dark

  • Bay Watcher
  • If you wont let me Dream, I wont let you sleep.
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1840 on: March 01, 2012, 12:06:53 am »

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?
Logged
There are 10 types of people in this world. Those that understand binary and those that don't


Quote
My milkshake brings all the criminals to justice.

Nadaka

  • Bay Watcher
    • View Profile
    • http://www.nadaka.us
Re: if self.isCoder(): post() #Programming Thread
« Reply #1841 on: March 01, 2012, 12:16:33 am »

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?

Correct, I probably need to clarify. It only seeks in the cardinal direction most directly towards the destination until that direction is blocked and it then stops and starts flooding, even if it can still travel in a straight line that brings it closer to the destination.
Logged
Take me out to the black, tell them I ain't comin' back...
I don't care cause I'm still free, you can't take the sky from me...

I turned myself into a monster, to fight against the monsters of the world.

dreadmullet

  • Bay Watcher
  • Inadequate Comedian
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1842 on: March 01, 2012, 01:34:50 am »

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?

Correct, I probably need to clarify. It only seeks in the cardinal direction most directly towards the destination until that direction is blocked and it then stops and starts flooding, even if it can still travel in a straight line that brings it closer to the destination.

That's just how A* works. To my knowledge, it's the best algorithm that will always produce the shortest path in an efficient way.

I can change one variable that will kind of make it do what you describe. If I increase the heuristic multiplier (hMult) from 1 to 10, it will be more aggressive in testing nodes that are closer to the destination. In your example, it would be faster, since it would branch out into less nodes. However, consider this example:

Code: [Select]
XXXXXXXXXXXXXXXXXX
X          B     X
XXXXXXXXXXXXXXXX X
X              X X
X              X X
X              X X
XA               X
XXXXXXXXXXXXXXXXXX

With hMult = 1 and hMult = 10, it will probably test the same amount of nodes each. More importantly, if hMult is greater than 1, it may generate a suboptimal path. I suspect in this case it would start to move toward B, and then move back into the optimal route. This article has some excellent animations.
Logged

Wolfy

  • Bay Watcher
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1843 on: March 01, 2012, 01:37:01 am »

I've done some things but nothing majoir, TBH I can never for the life of me, use what I learn, I can tell you what evrything dose and if you ask me what I think you need, I can get you something that works, but if I'm doing it I draw blanks.
Logged
I'm a bad speller, no amount of telling me how bad I am is going to make me better. People have been trying for over two decades. English is hard for me, its like how some cant get math, i cant get English.

MadocComadrin

  • Bay Watcher
  • A mysterious laboratory goblin!
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #1844 on: March 01, 2012, 01:40:39 am »

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?
In a 2d grid world, it depends on the shape used to make a grid. In a square grid, you have 4 directions that can take you from a center of one square to the center of another in 1 square's length. Any other direction takes a longer "step." A regular-octagon-based grid has 8 of these directions.


Spoiler (click to show/hide)
Logged
Pages: 1 ... 121 122 [123] 124 125 ... 796