Faits:
A.
A.X._ et B.X._ sont propriétaires du bien-fonds no xxx du cadastre de Chézard-St-Martin sur lequel se trouve leur maison. La parcelle est desservie au sud par la rue D._.
Le 30 juin 2003, C._ SA a déposé une demande portant sur la construction de quatre immeubles résidentiels de trois lofts chacun et sept villas individuelles avec garage à l'est de la parcelle des époux X._, dans le prolongement de la rue D._. L'enquête publique effectuée à la suite de la demande du permis de construire a été publiée deux fois dans la Feuille officielle, soit les 28 mai et 4 juin 2004.
Le 23 juin 2004, B.X._ a adressé une lettre au Conseil communal de Chézard-St-Martin (ci-après le Conseil communal). Déclarant ne pas s'opposer aux travaux prévus, mais craignant pour la résistance de la route et partant pour son immeuble, il demandait qu'un constat des lieux soit établi avant la mise en chantier et que les éventuels dégâts dus au passage de poids lourds devant son domicile soient pris en charge par le maître d'oeuvre.
Une séance de conciliation s'est tenue le 16 août 2004 entre les promoteurs, les opposants, le Conseil communal et B.X._, qui n'apparaissait pas comme opposant.
Le 14 octobre 2004, le Conseil communal a envoyé une lettre à B.X._, lui expliquant que l'accès au nouveau lotissement par la rue D._ ne durerait que le temps des travaux et qu'il était certain que ce chemin serait à terme remplacé, comme seul accès aux nouvelles habitations, par la nouvelle route qui serait construite après la levée des oppositions et la liquidation des éventuelles procédures d'expropriation.
Lors d'une séance extraordinaire du 30 octobre 2006, le Conseil communal a rappelé que l'autorisation de construire le nouveau quartier était liée à la réalisation de la nouvelle route. Lors d'une séance du 27 avril 2009, le Conseil communal a relevé que, compte tenu des implications financières, des procédures juridiques longues et incertaines et d'un renforcement des exigences en matière de zone à bâtir et d'utilisation du sol, la Commune n'avait pas d'assurance légale de construire cette nouvelle route.
Le 9 novembre 2009, la Commune a adopté un arrêté limitant la vitesse maximale à 20 km/h sur la rue D._, donnant la priorité aux piétons, restreignant le parcage aux endroits prévus et prévoyant que ce chemin serait signalé comme sans issue. Le recours formé par B.X._ contre cet arrêté a été rejeté, le 8 septembre 2011, par le Département de la gestion du territoire du canton de Neuchâtel.
A.X._ et B.X._ ont mandaté un expert pour déterminer la dépréciation de leur immeuble en raison de l'accès au nouveau lotissement, qui l'a chiffrée à 117'000 fr.
B.
Le 5 décembre 2011, les époux X._ ont formé une demande d'indemnisation auprès de la Commune. Le Conseil communal a répondu, le 8 mars 2012, qu'il ne pouvait y être donné suite.
Le 12 juin 2012, A.X._ et B.X._ ont ouvert action devant la Cour de droit public du Tribunal cantonal neuchâtelois (ci-après le Tribunal cantonal), concluant au versement par la Commune de 117'000 fr. plus intérêt à 5 % l'an dès le 7 février 2011 à titre d'indemnisation. Ils ont fait valoir en substance que le Conseil communal leur avait affirmé qu'une nouvelle route serait réalisée pour accéder au nouveau lotissement et que le nouveau quartier n'engendrerait aucun désagrément. Sur la base de ces promesses, ils n'avaient pas recouru contre l'autorisation de construire délivrée à C._ SA. Or, finalement, le Conseil communal avait changé d'avis pour des raisons purement économiques, ce qui avait entraîné une dépréciation de leur bien-fonds. Ils estimaient que ce changement d'avis, malgré les garanties fournies, était contraire à la bonne foi et constituait un comportement illicite.
Par arrêt du 28 mai 2013, le Tribunal cantonal a rejeté la demande.
C.
Contre cet arrêt, A.X._ et B.X._ forment un recours en matière de droit public auprès du Tribunal fédéral. Invoquant l'arbitraire et une violation de leur droit d'être entendu, ils concluent à l'annulation de l'arrêt du 28 mai 2013 et au renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des motifs de leur recours. Ils demandent par ailleurs la production des dossiers cantonaux.
Le Tribunal cantonal n'a pas formulé d'observations, se référant aux motifs de l'arrêt attaqué et concluant au rejet du recours. Dans ses déterminations, la Commune a précisé que, depuis le premier janvier 2013, elle avait fusionné avec diverses autres communes et formait désormais avec ces entités la Commune du Val-de-Ruz, qui était de ce fait la partie intimée à la présente procédure. Sur le fond, elle propose le rejet du recours.

Considérant en droit:
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 439).
1.1. Le litige concerne la responsabilité étatique fondée sur la loi neuchâteloise sur la responsabilité des collectivités publiques et de leurs agents du 26 juin 1989 (loi sur la responsabilité, LResp; RSN 150.10), soit sur du droit public cantonal. L'arrêt attaqué est donc en principe susceptible de faire l'objet d'un recours en matière de droit public au Tribunal fédéral (<ref-law>), la cause ne relevant pas du domaine de la responsabilité de l'Etat pour les activités médicales, pour lequel la voie du recours en matière civile est exceptionnellement ouverte (cf. <ref-law> et 31 al. 1 let. d RTF - RS 173.110.131 -; <ref-ruling> consid. 2.1 p. 465).
1.2. Dirigé contre un jugement final (<ref-law>) rendu par une autorité judiciaire cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2) et formé par les destinataires de l'arrêt attaqué qui ont intérêt à recourir (<ref-law>), le présent recours est en principe recevable comme recours en matière de droit public, la valeur litigieuse dépassant la limite de 30'000 fr. prévue à l'<ref-law> en matière de responsabilité étatique. Le mémoire a par ailleurs été déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>), étant précisé qu'en matière de droit public, des conclusions en renvoi, malgré le pouvoir de réforme du Tribunal fédéral (cf. <ref-law>), sont admissibles (<ref-ruling> consid. 1.4 p. 414 s.). Il convient donc d'entrer en matière.
1.3. La Commune intimée qui, initialement, était celle de Chezard-St-Martin est devenue, à la suite d'une fusion avec d'autres communes et depuis le 1er janvier 2013, la Commune du Val-de-Ruz (cf. art. 2 ch. 4 de la loi neuchâteloise sur les communes du 21 décembre 1964; RSN 171.1). La Commune de Chezard-St-Martin n'existe ainsi plus dès le 1er janvier 2013 et a été remplacée juridiquement par la nouvelle Commune du Val-de-Ruz. Il y a donc lieu de procéder à une substitution de partie (<ref-law> et 17 al. 1 PCF). Le recourant y consent, dès lors qu'il a lui-même dirigé son recours contre la Commune du Val-de-Ruz. Le fait que l'arrêt attaqué, bien qu'il date du 28 mai 2013, indique par inadvertance encore la Commune de Chézard-St-Martin n'y change rien.
1.4. Les autorités cantonales concernées ont produit leur dossier (cf. <ref-law>), rendant sans objet la requête en production desdits documents par les recourants.
2.
Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Il peut donc être formé pour violation d'un droit constitutionnel (<ref-ruling> consid. 2.1 p. 247; <ref-ruling> consid. 2.4 p. 313). En revanche, il ne peut pas être formé pour violation du droit cantonal; la partie recourante ne peut se plaindre de l'application du droit cantonal qu'en invoquant la violation d'un droit constitutionnel, en particulier l'interdiction de l'arbitraire (<ref-ruling> consid. 1.2 p. 382 s.). Par exception à la règle selon laquelle il applique le droit d'office (cf. <ref-law>), le Tribunal fédéral ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (<ref-law>; cf. en lien avec la responsabilité étatique, arrêt 4A_329/2012 du 4 décembre 2012 consid. 1.3, in SJ 2013 I 289).
3.
Se fondant sur les principes de droit privé fédéral en matière de responsabilité civile, les juges cantonaux ont considéré en substance que les recourants n'avaient pas subi une atteinte directe à un droit absolu, tel leur droit de propriété, mais faisaient valoir un préjudice purement patrimonial, de sorte que l'illicéité ne pouvait résulter de la seule atteinte qu'ils invoquaient. Quant à la violation du principe de la bonne foi soulevée par les recourants à l'appui de leur demande, elle ne permettait en tous les cas pas de fonder leur action. En effet, ils alléguaient qu'à la suite des promesses du Conseil communal selon lesquelles l'accès définitif aux nouvelles constructions ne passerait pas devant leur terrain, ils avaient renoncé à recourir contre l'autorisation de construire. Or, à supposer que l'on puisse considérer que le courrier du 14 octobre 2004 de la Commune ait contenu de telles assurances, les recourants n'étaient de toute façon plus en mesure de recourir contre la décision du permis de construire selon le droit cantonal, car ils n'avaient pas fait opposition pendant le délai d'enquête qui expirait le 28 juin 2004. Partant, les recourants ne pouvaient s'être fondés sur ces assurances pour prendre des dispositions auxquelles ils ne pouvaient plus renoncer.
4.
Les recourants reprochent en premier lieu aux juges cantonaux d'avoir interprété de manière arbitraire l'art. 5 al. 1 LResp en refusant d'admettre d'emblée l'existence d'un acte illicite de la part de la Commune lié à une atteinte directe à leur droit de propriété.
4.1. L'article 5 al. 1 LResp est la première disposition du chapitre 2 section 1 de la loi, qui est consacré à la responsabilité de la collectivité publique envers les tiers pour acte illicite. Selon cette disposition, la collectivité publique répond du dommage causé sans droit à un tiers par ses agents dans l'exercice de leurs fonctions, sans égard à la faute de ces derniers. Par analogie avec la jurisprudence rendue en lien avec l'art. 3 de la loi fédérale du 14 mars 1958 sur la responsabilité de la Confédération (RS 170.32; cf. <ref-ruling> consid. 4.1 p. 317), le terme " sans droit " figurant à l'art. 5 al. 1 LResp doit être compris comme signifiant " de manière illicite " (arrêt 2C_158/2010 du 18 août 2010 consid. 3.1). La notion d'illicéité est pour sa part définie par le droit privé fédéral, qui s'applique en l'occurrence à titre de droit cantonal supplétif conformément à l'art. 3 LResp. Le pouvoir d'examen de la Cour de céans est donc limité à la violation des droits constitutionnels invoqués, à savoir l'arbitraire (cf. supra consid. 2).
4.2. En pratique, si le fait dommageable consiste dans l'atteinte à un droit absolu (comme la vie ou la santé humaines, ou le droit de propriété), l'illicéité est d'emblée réalisée, sans qu'il soit nécessaire de rechercher si et de quelle manière l'auteur a violé une norme de comportement spécifique; on parle à ce propos d'illicéité par le résultat ( "Erfolgsunrecht "). Si, en revanche, le fait dommageable constitue une atteinte à un autre intérêt (par exemple le patrimoine), l'illicéité suppose qu'il existe un " rapport d'illicéité ", soit que l'auteur ait violé une norme de comportement ayant pour but de protéger le bien juridique en cause; c'est ce que l'on appelle l'illicéité par le comportement ( "Verhaltensunrecht "). En effet, le patrimoine en soi n'est pas un bien juridique, son atteinte donc pas illicite à elle seule (<ref-ruling> consid. 8.2 p. 188). En d'autres termes, la simple lésion du droit patrimonial d'un tiers n'emporte pas, en tant que telle, la réalisation d'un acte illicite; il faut encore qu'une règle de comportement de l'ordre juridique interdise une telle atteinte et que cette règle ait pour but la protection du bien lésé (<ref-ruling> consid. 4.2 p. 141; <ref-ruling> consid. 2.4 p. 376; <ref-ruling> consid. 4.1 p. 318).
4.3. Contrairement à ce que soutiennent les recourants, le Tribunal cantonal n'a nullement procédé à une application insoutenable de la notion d'illicéité en considérant que le dommage qu'ils invoquaient était un préjudice purement patrimonial. En effet, l'immeuble propriété des recourants n'a pas été endommagé; ceux-ci ne sont pas restreints dans l'usage de leur terrain, ni dans l'accès à leur maison. On ne voit pas du reste qu'ils se trouvent privés d'un attribut de leur droit de propriété. En considérant que la perte de la valeur vénale alléguée ne constituait pas une atteinte à un droit absolu, d'emblée illicite, mais une atteinte patrimoniale, les juges cantonaux n'ont donc pas interprété arbitrairement l'art. 5 al. 1 LResp.
5.
A titre subsidiaire, les recourants s'en prennent au refus de l'arrêt attaqué d'admettre un acte illicite en lien avec la violation du principe de la bonne foi. Ils invoquent à cet égard l'arbitraire et la violation de leur droit d'être entendu, reprochant au Tribunal cantonal d'avoir considéré que, n'ayant pas fait opposition à la délivrance de l'autorisation de construire, le courrier du 14 octobre 2004 ne pouvait les avoir incités à ne pas recourir, puisqu'ils n'étaient de toute façon pas en droit de le faire, le recours étant réservé aux opposants.
5.1. Découlant directement de l'art. 9 Cst. et valant pour l'ensemble de l'activité étatique, le principe de la bonne foi protège le citoyen, à certaines conditions, dans la confiance légitime qu'il met dans les assurances reçues des autorités, notamment lorsqu'il a réglé sa conduite d'après des décisions, des déclarations ou un comportement déterminé de l'administration et qu'il a pris sur cette base des dispositions qu'il ne saurait modifier sans subir de préjudice (<ref-ruling> consid. 2.5.1 p. 73; <ref-ruling> consid. 6.1 p. 636; <ref-ruling> consid. 8.1 p. 60; <ref-ruling> consid. 7.1 p. 381). Si les conditions sont réunies, la conséquence juridique qui en découle est, en premier lieu, que l'autorité est liée par les assurances données. Il peut toutefois arriver que, même en présence d'une violation du principe de la bonne foi, le respect des assurances données doive s'effacer devant un intérêt public supérieur qui l'emporte sur l'intérêt privé que l'administré fait valoir. Il appartient alors à l'administré, à la place d'obtenir le respect des assurances données, de réclamer la réparation du préjudice qu'il a subi (cf. <ref-ruling> consid. 6c p. 331). La violation du principe de la bonne foi peut, dans un tel cas, notamment constituer un acte illicite au sens de la responsabilité étatique (arrêts 2C_502/2013 du 30 septembre 2013 consid. 2.1; 2A.511/2005 du 16 février 2009 consid. 5.5.2 et 5.5.3).
5.2. Les recourants reprochent tout d'abord au Tribunal cantonal d'avoir retenu, sans aucune motivation juridique, en violation de leur droit d'être entendu, que leur courrier du 23 juin 2004 ne constituait pas une opposition.
Une telle critique ne relève pas du droit d'être entendu. En effet, l'obligation de motiver, telle qu'elle découle du droit d'être entendu, est respectée lorsque l'intéressé peut se rendre compte de la portée de la décision et l'attaquer en connaissance de cause. Selon la jurisprudence, la motivation d'une décision est suffisante lorsque l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé son raisonnement (<ref-ruling> consid. 3.2 p. 270; <ref-ruling> consid. 5.2 p. 236; <ref-ruling> consid. 4.3 p. 540). Dès lors que l'on peut discerner les motifs qui ont guidé la décision de l'autorité, le droit à une décision motivée est respecté même si la motivation présentée est erronée (arrêts 1B_48/2013 du 19 février 2013 consid. 2.1; 2C_724/2012 du 25 juillet 2012 consid. 5.1). Le point de savoir si la motivation présentée est correcte ne relève ainsi pas du droit d'être entendu.
En l'espèce, les juges cantonaux ont expliqué pourquoi ils ont considéré que les recourants n'avaient pas formé opposition dans leur courrier du 23 juin 2004 en reproduisant un extrait de ce courrier dans lequel B.X._ indiquait expressément ... " Je ne m'oppose pas aux travaux prévus, mais demande expressément qu'un constat de l'état des lieux soit établi avant la mise en chantier et que les éventuels dégâts soient pris en charge par le maître d'oeuvre. D'avance, je vous remercie de prendre en considération ma remarque. ". Une telle position permet de comprendre le raisonnement des juges cantonaux et le recourant a été à même de le saisir et de l'attaquer. On ne discerne donc manifestement aucune violation de l'obligation de motiver.
Lorsque les recourants soutiennent que les juges n'ont pas motivé juridiquement pourquoi ce texte ne constituait pas une opposition, ils s'en prennent à la portée juridique donnée à la lettre du 23 juin 2004. Une telle critique ne relève nullement du droit d'être entendu, mais du fond. Or, si les recourants entendaient formuler une telle critique, ils leur appartenaient d'expliquer en quoi l'interprétation donnée à ce courrier procédait d'une application arbitraire des règles cantonales régissant les oppositions en matière de construction (cf. <ref-law>). Faute de grief, il n'appartient pas au Tribunal fédéral d'entrer d'office plus avant sur cette question qui relève du droit cantonal (cf. supra consid. 2).
5.3. En second lieu, les recourants soutiennent qu'ils " n'ont que mollement réagit (recte : réagi) au projet de construction ", car ils auraient reçu, avant l'échéance du délai pour former opposition, des assurances de l'autorité communale que le projet ne serait autorisé qu'à la condition que la nouvelle route projetée soit construite. Ils auraient proposé des offres de preuves pour le démontrer auxquelles le Tribunal cantonal n'aurait arbitrairement pas donné suite, violant leur droit d'être entendu.
Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend notamment le droit pour l'intéressé de produire des preuves pertinentes et d'obtenir qu'il y soit donné suite (<ref-ruling> consid. 2.2 p. 504 s.; <ref-ruling> consid. 2b p. 56; <ref-ruling> consid. 2a/aa p. 16 et les arrêts cités). L'autorité de décision peut donc se livrer à une appréciation anticipée de la pertinence du fait à prouver et de l'utilité du moyen de preuve offert et, sur cette base, refuser de l'administrer. Ce refus ne viole le droit d'être entendu que si l'appréciation à laquelle elle a ainsi procédé est entachée d'arbitraire (<ref-ruling> consid. 3 p. 157 et les arrêts cités; sur la notion d'arbitraire, voir <ref-ruling> consid. 5.1 p. 17).
En l'espèce, les recourants soutiennent, devant le Tribunal fédéral, qu'ils auraient proposé, en annexe à leur demande du 12 juin 2012, l'audition d'un témoin et de trois conseillers communaux pour démontrer que, dans le délai pour former opposition, ils auraient déjà reçu des assurances que l'accès définitif aux nouvelles constructions ne passerait pas par la rue D._. Or, il se trouve que, dans leur écriture sur le plan cantonal, ils n'ont jamais prétendu avoir été incités à ne pas former opposition dans le délai expirant à fin juin 2004, mais seulement à ne pas recourir, à la suite des assurances données par écrit le 14 octobre 2004. De plus, dans leur bordereau des autres moyens de preuves produit sur le plan cantonal, il n'y a aucune indication relative aux faits que les témoins étaient censés éclaircir. On ne voit dès lors pas en quoi on pourrait reprocher au Tribunal cantonal d'avoir violé l'art. 29 al. 2 Cst. en lien avec une appréciation anticipée des preuves, en ne donnant pas suite à des offres de preuve en lien avec une argumentation que les recourants eux-mêmes n'avaient pas soulevée devant l'instance cantonale. La critique est manifestement dépourvue de tout fondement.
Le recours ne peut donc qu'être rejeté.
6.
Compte tenu de l'issue du litige, les frais doivent être mis à la charge des recourants, solidairement entre eux (art. 66 al. 1 et 5 LTF). En vertu de l'art. 68 al. 1 et 4 LTF, ils supporteront à titre solidaire les dépens auxquels la Commune intimée, représentée par un avocat dans un procès en responsabilité, peut prétendre, l'<ref-law> ne s'appliquant pas (cf. arrêt 2C_852/2011 du 10 janvier 2012 consid. 6 et l'arrêt cité).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 5'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3.
Une indemnité de 4'000 fr., à payer à la Commune du Val-de-Ruz à titre de dépens, est mise à la charge des recourants, créanciers solidaires.
4.
Le présent arrêt est communiqué aux mandataires des parties et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public.
Lausanne, le 28 octobre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Vuadens